백준 / 11657 타임머신 C++

www.acmicpc.net/problem/11657

11657번: 타임머신

버스를 차고 1번 노드에서 해당 노드까지 최단 시간 (거리)를 구하는 문제입니다.

음수인 가중치가 허용되므로 다익스트라 알고리즘이 아닌 벨만 포드 알고리즘을 이용해야합니다.

 

벨만 포드 알고리즘

 

벨만 포드 알고리즘은 기준 노드에서 다른 노드까지 최단 경로를 찾을 때 이용됩니다. 복잡도는 다익스트라보다 좋지 않지만, 음수 가중치를 허용하는 경우 벨만 포드 알고리즘을 이용해야합니다.

 

벨만 포드 알고리즘은 다음과 같은 과정으로 진행됩니다.

 

1. 모든 노드 값을 무한대 (inf)로 잡는다.

 

2. 기준 노드의 값을 정한다. (여기서는 1번에서 1번 노드로 가는 시간이 0이므로 0으로 잡았습니다.)

 

3. 모든 간선을 n-1번 (n=전체 노드 수) 탐색하면서 간선이 잇는 출발 노드가 한 번이라도 계산된 노드면 해당 간선의 도착 노드의 값을 비교하여 최솟값으로 업데이트한다.

( 1번 노드 -> 2번 노드로의 가중치가 3이고, 2번 노드의 값이 inf면, 2번 노드 값을 3으로 업데이트, 2번 노드의 값이 5이면 2번 노드의 값을 3으로 업데이트 등)

 

 4. 음의 사이클이 발생하는 지 확인한다. 모든 간선을 탐색하면서 다시 업데이트가 되는 곳이 있다면, 그 곳은 음의 사이클이 발생하는 곳이다. 

( 3번 노드 -> 4번 노드로의 가중치가 -5, 4번 노드의 값이 -10이면 4번 노드는 -15로 업데이트, 다시 돌아오면 4번 노드는 -20, ...., 와 같이 음의 무한대 값을 가지므로 최솟값이 의미가 없어짐. 그러므로 음의 사이클을 갖는다.)

 

문제 풀이

벨만 포드 알고리즘을 적용하여 풀었습니다. 음의 사이클을 갖는 경우는 -1을 출력하고, 해당 노드의 값이 inf면 그 노드는 1번 노드에서 가는 경로가 없다는 의미이므로 -1을 출력합니다. 그리고 거리 (시간) 배열 (벡터)을 int로 잡으면 주어진 조건에서 모든 가중치가 -10,000 또는 모든 가중치가 10,000 이라 하면 오버플로우가 발생합니다.

( 500 * 600 * 10,000 = 3,000,000,000 ) 그러므로 long long으로 잡았습니다. 

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, m;
long long inf = 9223372036854775807; // 무한대
vector<long long>v; // 각 노드 최단 시간 (v[1] : 출발) 
vector<pair<pair<int, int>, int>>edge; // {{출발, 도착}, 가중치}
int check = 0;

void make_bus()
{
	cin >> n >> m;
	v.resize(n + 1, inf);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back({ {a,b},c });
	}
}

void Bellman_Ford()
{
	// 1번 노드 0으로 
	// n-1 번 돌면서 계산 안 된 출발 노드 (inf) 넘어가기
	// 한 번이라도 계산된 출발 노드면 업데이트

	v[1] = 0;
	for (int i = 1; i <= (n - 1); i++) {
		for (int j = 0; j < edge.size(); j++) {
			int from = edge[j].first.first;
			int to = edge[j].first.second;
			int cost = edge[j].second;

			if (v[from] == inf)
				continue;
			if (v[to] > (v[from] + cost))
				v[to] = (v[from] + cost);
		}
	}

	// 모든 edge에 대해 한 번 더 탐색하면서 정상 그래프인지 판단
	// 해당 노드 값이 inf면 1번에서 출발하여 가는 경로 없음
	// 업데이트가 다시 일어나면 음의 사이클 존재 : 무한히 작아지므로 비정상 그래프

	for (int i = 0; i < edge.size(); i++) {
		int from = edge[i].first.first;
		int to = edge[i].first.second;
		int cost = edge[i].second;

		// from 노드 가는 경로 X
		if (v[from] == inf) 
			continue;

		// 비정상 그래프 : check = -1로 잡음
		if (v[to] > (v[from] + cost)) {
			check = -1;
			return;
		}
	}
}

int main()
{
	make_bus();
	if (n == 1)
	{
		cout << 0;
		return 0;
	}

	Bellman_Ford();

	if (check == -1)
	{
		cout << -1;
		return 0;
	}

	else {
		for (int i = 2; i <= n; i++) {
			if (v[i] == inf)
				cout << -1 << '\n';
			else
				cout << v[i] << '\n';
		}
	}
}