[백준/C++] 타임머신

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 음의 간선이 있기 때문에, Dijikstra알고리즘으로 문제를 풀 수 없다.

음의 사이클이 존재하는지 찾는 알고리즘에는 벨만 포드 알고리즘이 있기 때문에 벨만 포드 알고리즘을 이용해 문제를 풀었다.

 

벨만 포드 알고리즘에서 음의 사이클이 존재하는지 판단하는 방법은 다음과 같다.

 

N개의 정점이 있을 때, 임의의 정점 A에 도달하기 위해 거쳐야되는 정점의 개수는 총 N-1개다.

 

그렇기 때문에 음의 사이클이 없다면 임의의 정점에서 다른 정점으로 도달하는 최소비용을 구하는 과정을 N-1번 하면 출발 정점에서 모든 정점에 도달하는 최단경로가 계산이 된다.

 

이 때, 음의 사이클이 있다면 한번 더 최단경로를 계산했을 때, 임의의 정점에 도달하는 최소비용이 바뀌게 된다.

이를 이용해 음의 사이클이 존재하는지 판단 할 수 있다.

 

여기서 중요한 점은 음의 간선이 있기 때문에 최소비용을 구하는 과정에서 언더플로우가 날 수 있다는 점이다.

 

그렇기 때문에 변수의 타입을 long long으로 선언해 문제를 풀어주어야 한다.

 

+ 코드를 구현할 때, 벨만 포드 알고리즘을 완전 따라하지는 않았다.

모든 간선에 대해 체크를 하지 않고, INF값이 아닌 정점 즉, 방문할 수 있는 정점이라면 그 정점에서 다른 정점으로 가는 최단거리 비용을 계산했다.

그렇기 때문에 내가 구현한 코드에서 최단거리 비용의 범위는 -500*500*10000 ~ 500*10000 사이이다.

 

​

[아이디어 정리]

1. 임의의 정점의 값이 INF가 아니라면 방문할 수 있는 정점이므로, 그 정점에서 다른 정점으로 가는 최소시간을 계산해 갱신했다.
2. 1번 과정을 N번 반복하고, 만약 N번째 에서 값이 바뀐다면 음의 사이클이 있다는 뜻이므로 -1을 출력한다.
3. 음의 사이클이 없다면 저장된 최소 시간을 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


const long long INF =5000000;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N,M;
	cin >> N>>M;
	vector<vector<pair<int, long long>>> graph(N + 1);
	int A, B, C;
	for (int i = 0; i < M; i++) 
	{
		cin >> A >> B >> C;
		graph[A].push_back(make_pair(B, C));
	}

	vector<long long> visited(N + 1, INF);
	pair<int, long long>np;
	visited[1] = 0;
	for (int i = 0; i < N; i++) 
	{
		for (int j = 1; j <= N; j++) 
		{
			if (visited[j] != INF) // 방문할 수 있는 정점이라면
			{
				for (int k = 0; k < graph[j].size(); k++)
				{
					np = graph[j][k];
					if (visited[np.first] > visited[j] + np.second) 
					{
						visited[np.first] = visited[j] + np.second;
						if (i == N - 1) 
						{
							cout << -1;
							return 0;
						}
					}
				}
			}
		}
	}

	for (int i = 2; i <= N; i++) {
		if (visited[i] == INF) {
			cout << -1 << "\n";
		}
		else {
			cout << visited[i] << "\n";
		}
	}
	
	return 0;
}

 

---

처음에 언더플로우의 가능성에 대해 전혀 고려하지 않아서 왜 출력 초과가 날까 고민했다.

알고보니 내가 구현한 코드에서는 -25억의 범위가 가능해서 언더플로우가 나는 것이었다.

다른 사람들을 수의 범위가 -500*6000*10000 이라길래 왜 그런지 이해가 안됐는데 구현한 코드의 내용이 달랐다...

나중에 찾아보니 내 코드는 벨만 포드와 개선된 벨만 포드 알고리즘인 SPFA 사이의 어떤 무언가의 코드가 되어 있었다... ㅋㅋㅋㅋ