[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

우선 이 문제를 풀기위해서는 벨만-포드 알고리즘을 이해해야한다.

벨만-포드

단일시작점 알고리즘 (출발 노드가 고정) 최단 경로 알고리즘 음수 간선 가능 음수 사이클 확인 가능

쓱 보면 다익스트라와 비슷해보인다.(https://guccin.tistory.com/112?category=977502)

그러나 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선에 대해서 최단거리를 알아낼수 있다.

또한 다익스트라는 우선순위 큐를 활용하여 최단 경로를 구하는데에 반해 벨만-포드는 매번 모든 간선을 전부 확인하며 최단거리를 알아내기 때문에 다익스트라보다 시간복잡도가 크다. 다익스트라 O(|E||log|V|), 벨만-포드 O(|E||V|)

벨만-포드 진행과정

최단거리 테이블 초기화 출발노드 설정 V번 루프를 돈다. 중간노드 루프를 돈다. 중간노드의 간선들을 확인하여 upper 배열을 완화시킨다. V번째 루프에서 음수사이클이 존재하는지 판단한다.(완화가 일어났는지 확인)

그럼 대강 알았으니 더 공부하기 위해서는 동빈나님의 영상을 참고하면 좋을것 같다.(https://www.youtube.com/watch?v=Ppimbaxm8d8)

이제 문제에 접근해보자

문제에서 주어지는 것은 그래프의 노드 개수와 간선 정보이다. 여기서 주요 포인트는 아래와 같다.

* 양수가 아닌 음수 가중치가 존재한다.

* 출발지가 1로 고정되기 때문에 단일 시작점 알고리즘이다.

* 시간을 무한히 오래전으로 되돌릴수 있다는 의미는 음수 사이클이 존재할 수 있다는 소리다.

그렇다면 결론적으로 다익스트라를 사용할 수 없다. 따라서 음수 가중치의 최단 경로를 구할 수 있고 음수 사이클까지 확인 가능한 벨만-포드 알고리즘을 사용해야 한다.

그럼 이를 토대로 코드를 짜면된다.

이때 주의해야 할 것은 가중치의 최댓값이 int가 아닌 long long이어야 한다는점.

또한, 언더플로우와 오버플로우를 막기 위해 중간노드의 최단거리가 이미 INF라면 연산을 생략해준다는 점이다.

#include #include #include #define MAX_N 501 #define INF 200000000000000000 using namespace std; int N, M; vector> adj[MAX_N]; void bellman() { // upper를 INF로 초기화, src 초기화 vector upper(N + 1, INF); upper[1] = 0;//1에서 1로 가는 경우 비용 0 // 완화 체크 int updated = 0; // v만큼 반복 for (int iter = 0; iter < N; iter++) { updated = 0; for (int here = 1; here <= N; here++)//S -> 들러갈 노드(here) for (int j = 0; j < adj[here].size(); j++)// S -> 들러갈 노드 -> 도착 노드(adj[here][j]) { int end = adj[here][j].first; int cost = adj[here][j].second; // 중간노드까지의 값이 INF라면 의미가 없는것은 물론, // 언더플로우나 오버플로우가 일어날 가능성이 존재한다. if (upper[here] == INF) continue; if (upper[end] > upper[here] + cost) { upper[end] = upper[here] + cost; updated = 1; } } if (updated == 0)// 이건 왜 들어가야하는지 정확히 모르겠다. break; } // 마지막 V번째 루프(음수사이클 판별)에서 완화가 일어났으면 음수 사이클 존재 if (updated == 1) { upper.clear(); cout << -1 <<'

'; return; } for (int i = 2; i <= N; i++) { if (upper[i] != INF) cout << upper[i] << '

'; else cout << -1 << '

'; } } int main() { // 단일 시작점 알고리즘, 음수가중치 존재 // 음수 사이클 존재 가능, 경로 없는 경우 가능 cin >> N >> M; int A, B, C; for (int i = 0; i < M; i++) { cin >> A >> B >> C; adj[A].push_back({ B,C }); } bellman(); }

이를 코드로 짜는 것은 얼마 걸리지 않았지만, 문제는 제출이 안되고 계속 틀렸다. 알고보니 언더플로우와 오버플로우를 예상하지 못했다. 이는 실제 프로그래밍에서 더 심각한 문제를 발생할 수 있기때문에 더 주의해야한다.

결론 : 벨만-포드는 음수 가중치, 음수 사이클, O(VE) 등등의 속성을 가진다는 것을 잘 머리에 박아놓자.

from http://guccin.tistory.com/114 by ccl(A) rewrite - 2021-08-06 18:00:28