[백준/c++] 11657번 - 타임머신

[ 문제 ]

 

 

[ 구현 ]

 

음의 간선이 존재하는 최단거리 그래프 문제이므로 벨만-포드 알고리즘을 이용해야 한다.

 

이때 벨만-포드 알고리즘의 핵심적인 부분을 간단하게 요약해보면

초기에 출발점을 0, 나머지 모든 정점들을 INF로 설정하고

정점의 개수가 N개 일때 N-1번만 루프를 돌아주면 dist배열에 저장된 거리가 최단거리인데

 

거리를 갱신할 때의 조건을 잘 이해하는 것이 핵심이다.

if(dist[j] != INF && dist[next] > dist[j] + cost) {

     dist[next] = dist[j] + cost;

}

 

우선 dist[j] !=INF가 의미하는 것은 출발점으로부터 현재 접근이 가능한 상태인 정점인 경우를 의미하고

이 조건이 없으면 출발점에서 절대 갈 수 없는 정점을 통해서도 거리의 갱신이 일어날 수 있기 때문에 필요하다.

(1->2 거리 3,

 2->3 거리 4,

 5->4 거리 -1인 상황을 가정해보면

출발점이 1인 경우 5와 4는 절대로 갈 수 없는, 즉 거리가 INF인 점이지만

5를 통해 4의 거리를 INF-1로 잡아버리는 골때리는 상황이 발생하고

이후 출력에서 도달 불가능한 점을 걸러내기도 어려워짐)

 

 

dist[next] > dist[j] + cost는 다익스트라 알고리즘과 비슷하게

현재까지의 최단거리보다 다음 정점을 거쳐서 가는 거리가 더 적은 경우 업데이트해주기 위한 조건이다.

 

 

이렇게 n-1번의 사이클을 돌아서 최단거리를 구한 이후에 마지막으로 한 번 더 사이클을 돌아주는데,

이때 최단거리의 갱신이 일어나면 음의 사이클이 존재하는 것이므로 이 부분까지 신경써주면 된다.

 

 

 

[ 코드 ]

 

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

using namespace std;

int n, m;
vector<pair<int, int>> graph[501];
long long INF = 1e18;
long long dist[501];
bool minuscycle = false;

void bellmanFord(int n) {
	fill(dist + 1, dist + n + 1, INF);//1번부터 n번 정점까지의 거리 INF로 초기화
	dist[1] = 0;//1번 노드를 출발점으로 설정

	for (int i = 0; i < n; i++) {//마지막은 음의 사이클을 판단하기 위함
		for (int j = 1; j <= n; j++) {//각 사이클마다 모든 정점에 대해 거리를 확인하고 INF가 아니면 거리 갱신
			for(auto &x : graph[j]) {
				int next = x.first;
				int cost = x.second;

				if (dist[j] != INF && dist[next] > dist[j] + cost) {
					dist[next] = dist[j] + cost;

					if (i == n-1) {//n번째 사이클에서도 dist에 변화가 일어난다는 것은 음의 사이클이 존재한다는 뜻
						minuscycle = true;
						return;
					}
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;

		graph[a].push_back({ b,c });
	}

	bellmanFord(n);

	if (minuscycle) cout << -1;

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

	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

다익스트라 알고리즘은 이전에 이미 접해봤었던 것에 비해, 벨만-포드의 경우 뭔가 복잡하게 보여서 선뜻 공부하기 싫은 느낌이 굉장히 강했지만 감을 잡는데 크게 어려움이 없어서 다행이다.