백준 11657. 타임머신 [C++]

문제 : 타임머신

유형 : 그래프, 벨만포드

---

문제 해석

• 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

• 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. A에서 B도시로 가는데 양수가 아닌 음수가 있다.

해결 전략

• 일단 누가봐도 그래프 문제다. 근데 경로에 양수가 아닌 음수가 있다. 즉 벨만포드 알고리즘을 이용하여 풀 수 있다.

벨만포드 알고리즘

벨만포드 알고리즘 또한 다익스트라 알고리즘처럼 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다익스트라 알고리즘보다 시간이 더 걸리지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다.

벨만 포드 알고리즘은 다이나믹 프로그래밍이라고 할 수 있다. 그 이유는 매번 저장해놓은 최소 비용을 이용해서 새로운 최소 비용으로 갱신하기 때문이다.

벨만포드 알고리즘 동작원리

1. 시작 정점을 선택한다.
2. 모든 간선들을 탐색하면서, 시작 정점에서 다른 정점까지의 거리가 INF가 아니라면 거리를 갱신한다. 이 과정을 (정점의 수-1)번 만큼 진행한다.
3. 마지막으로 2번을 수행한다.

2번 과정에서 정점의 수-1번 만큼 진행하는 이유

V 개의 정점과 E 개의 간선이 있는 가중 그래프에서 어떤 정점 A에서 어떤 정점 B까지의 최단 거리는 최대 V-1개의 정점을 지나기 때문이다. V-1개 이상의 정점을 방문하는 것은 결국 중복 방문을 하는 것이기 때문에 최단 경로가 성립될 수 없다. 또한, 3번 과정에서 마지막으로 2번 과정을 한 번 더 수행하는 이유는 음의 사이클 유무를 판단하기 위해서이다. 만약 V 개의 정점을 지났는데 최단 경로가 갱신이 된다면 음의 사이클이 발생한 것이며 비용이 무한하게 갱신이 되기 때문에 최단 경로를 구할 수 없다.

설계, 구현

• 벨만포드 알고리즘을 구현하면 된다.

---

주의할 점

int dist[501]을 long long dist[501]로 변경

벨만포드는 모든간선을 정점의 개수만큼 반복해서 돈다.

dist범위는 간선의 개수 * 간선 비용 * 정점의 개수다.
즉 6000*10000*500 = 3*10^10 → int 범위 2147483647를 넘는다.

---

코드

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

struct st {
	int from;
	int to;
	int cost;
};

vector<st> edge;
long long dist[501];

void bellmanFord(int n, int m) {
	for(int i=1; i<=n; i++) dist[i] = INF;
	dist[1] = 0;
	
	for(int i=1; i<=n-1; i++) {
		for(int j=0; j<edge.size(); j++) {
			int from = edge[j].from;
			int to = edge[j].to;
			int cost = edge[j].cost;
			
			if(dist[from] == INF) continue;
			if(dist[to] > dist[from] + cost) dist[to] = dist[from] + cost;
		}
	}


	for(int j=0; j<edge.size(); j++) {
		int from = edge[j].from;
		int to = edge[j].to;
		int cost = edge[j].cost;
		
		if(dist[from] == INF) continue;
		if(dist[to] > dist[from] + cost) {
			cout << -1;
			return;
		}
	}
	
	
	for(int i=2; i<=n; i++) {
		// 해당 도시로 가는 경로가 없다.
		if(dist[i] == INF) cout << -1 << endl; 
		// 해당 도시로 가는 경로가 있다. 
		else cout << dist[i] << endl;
	}

}

int main() {
	int n, m;
	cin >> n >> m;
	for(int i=0; i<m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back({a, b, c}); // from, to, cost
	}
	
	bellmanFord(n, m);
	
	return 0;
}