[C/C++] 백준 1738번 골목길

✏️ 문제 링크

https://www.acmicpc.net/problem/1738

1738번: 골목길

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

벨만-포드 알고리즘을 이용하는 문제입니다. 처음에는 문제를 대충 읽고 벨만-포드를 돌린 후 음수 사이클의 여부에 따라서 정답을 출력하려고 했으나 문제를 다시 읽어보니 금품의 양이 최대가 되어야 한다는 점을 깨달았습니다. 그래서 방식을 고민하다가 입력받는 가중치를 음의 부호를 붙여서 입력받는 방식을 생각했습니다. 이렇게 하게 되면 자연스럽게 양의 가중치가 큰 것이 음에서는 제일 작아지기 때문에 최단 경로로 계산하게 됩니다. 위 방식대로 코드를 구현 후, N-1번 돌린 값과 N번 돌린 값을 비교하여 음의 사이클 여부를 판단하려고 했습니다. 하지만 76%에서 틀렸습니다..

#include<iostream>
#include<vector>
#include<tuple>
#include<limits.h>
using namespace std;

typedef tuple<int, int, int>edge;
int N, M;
int u, v, w;
vector<edge>edges; // 에지 리스트 
vector<int>before; // 마지막 경로 저장 배열
vector<int>path; // 경로 출력 배열
vector<long>mdist; // 골드의 양
void findPath(int node);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	before.resize(N + 1);
	mdist.resize(N + 1);
	fill(mdist.begin(), mdist.end(), LONG_MAX);

	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		edges.push_back(edge(u, v, -w));
	}


	mdist[1] = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < M; j++) {
			edge temp = edges[j];
			int start = get<0>(temp);
			int end = get<1>(temp);
			int value = get<2>(temp);

			if (mdist[start] != LONG_MAX && mdist[end] > mdist[start] + value) {
				mdist[end] = mdist[start] + value;
				before[end] = start;
			}
		}
	}

	bool isCycle = false;
	for (int j = 0; j < N; j++) {
		edge temp = edges[j];
		int start = get<0>(temp);
		int end = get<1>(temp);
		int value = get<2>(temp);

		if (mdist[start] != LONG_MAX && mdist[end] > mdist[start] + value) {
			isCycle = true;
			break;
		}
	}


	if (isCycle|| mdist[N] == LONG_MAX)
		cout << -1;
	else
	{
		findPath(N);
		for (int i = path.size() - 1; i >= 0; i--)
			cout << path[i] << " ";
		cout << N;
	}
}

void findPath(int node)
{
	int s = before[node];

	while (s != 0) {
		path.push_back(s);
		s = before[s];
	}

}

그래서 왜 그런가 싶었는데 질문 게시판을 찾아보니까 시간초과와 비슷한 원리로 안 되는 거더라구요

아니면 댓글 달아주세요 사실 잘 모르겠음..

 

그래서 방식을 바꿔서 한 번에 구하는 방식으로 바꿨습니다.

#include<iostream>
#include<vector>
#include<tuple>
#include<limits.h>
using namespace std;

typedef tuple<int, int, int>edge;
int N, M;
int u, v, w;
vector<edge>edges; // 에지 리스트 
vector<int>before; // 마지막 경로 저장 배열
vector<int>path; // 경로 출력 배열
vector<long>mdist; // 골드의 양
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	before.resize(N + 1);
	mdist.resize(N + 1);
	fill(mdist.begin(), mdist.end(), LONG_MAX);

	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		edges.push_back(edge(u, v, -w));
	}


	mdist[1] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			edge temp = edges[j];
			int start = get<0>(temp);
			int end = get<1>(temp);
			int value = get<2>(temp);

			if (mdist[start] != LONG_MAX && mdist[end] > mdist[start] + value) {
				mdist[end] = mdist[start] + value;
				before[end] = start;
				if (i == N - 1)
					mdist[end] = -LONG_MAX;
			}
		}
	}

	if (mdist[N] == LONG_MAX || mdist[N] == -LONG_MAX)
		cout << -1;
	else
	{
		int s = N;
		while (s != 0) {
			path.push_back(s);
			s = before[s];
		}
		for (int i = path.size() - 1; i >= 0; i--)
			cout << path[i] << " ";

	}
}

이번에는 메모리 초과로 96퍼에서 틀렸습니다가 나오더라구요...

그래서 그냥 배열들도 시작부터 크기를 지정해주고 보기 쉽게 MAIN함수에서 bellmanFord함수 호출식으로 하니까 맞았습니다.. 풀면 풀 수록 그냥 허수인 것 같습니다 하하

 

 

 

✏️ 문제 코드

#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

typedef pair< int, int>edge;
int N, M, u, v, w;
vector<edge>edges[101]; // 에지 리스트 
long mdist[101];
int before[101];
void bellmanFord();
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		edges[u].push_back({ v,-w });
	}

	bellmanFord();	
}

void bellmanFord()
{

	fill(mdist, mdist + 101, LONG_MAX);
	mdist[1] = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 1; j < N+1; j++) {
			for (edge tmp : edges[j]) {
				int start = j;
				int end = tmp.first;
				int value = tmp.second;
				if (mdist[start] != LONG_MAX && mdist[end] > mdist[start] + value) {
					mdist[end] = mdist[start] + value;
					before[end] = start;
					if (i == N - 1)
						mdist[end] = -LONG_MAX;
				}
			}
		}
	}

	if (mdist[N] == LONG_MAX || mdist[N] == -LONG_MAX)
		cout << -1;
	else
	{
		vector<int>path; // 경로 출력 배열
		int s = N;
		while (s != 0) {
			path.push_back(s);
			s = before[s];
		}
		for (int i = path.size() - 1; i >= 0; i--)
			cout << path[i] << " ";
	}
	return;
}

 

 

✏️ 더 보기

https://pooreumjung.tistory.com/322

[C/C++] 백준 14938번 - 서강그라운드

https://pooreumjung.tistory.com/321

[C/C++] 백준 1865번 - 웜홀

https://pooreumjung.tistory.com/300

Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜)