[백준] No.1865 - 웜홀 (C++, 벨만- 포드)

문제

 

https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

풀이

 

solved.ac 난이도: Gold 4

 

 

다익스트라는 음수 사이클의 존재 여부를 알 수 없으므로

음수 사이클의 존재 여부를 판정할 수 있는 벨만-포드(Bellman-Ford) 최단 경로 알고리즘을 사용하자.

 

벨만-포드 알고리즘이 음수 사이클의 존재 여부를 알 수 있는 이유는 다음과 같다.

벨만-포드에서는 모든 정점에서 간선으로 연결된 정점으로 이동하는 거리의 완화를 시도한다.

완화(relax)는 정점 v까지의 최단 cost(upper[v])가 u의 최단 경로(upper[u])에서 v로 이동하는 간선의 가중치 w(u,v)(=cost)를 통해 더 낮아지는 경우 일어난다.

cost + upper[u] < upper[v]

 

만약 가장 긴 최단 경로가 있다면 이는 시작점에서 시작하여 다른 모든 정점을 거쳐 도착점으로 이동하는 경로일 것이다.

정점의 개수를 V라고 할 때 1번 정점(시작 정점)에서 V정점(도착 정점)까지 거치는 간선의 개수는 총 V-1개이다.

완화(relax)는 간선을 거치면서 cost 비교를 통해 일어나므로 최단 경로를 만드는데 일어날 수 있는 최대 완화 횟수는 V-1이다.

따라서 V번째에도 완화가 일어난다면 이는 음수 사이클로 인해 무한히 완화가 일어나는 경우임을 알 수 있다.

(음수 사이클을 돌면, 해당 사이클에 포함된 정점들은 항상 완화가 진행되기 때문)

 

그러므로 벨만-포드를 통해 음수 사이클이 발견된다면

사이클에 포함된 정점에서는 해당 정점을 음수 cost로 되돌아 갈 수 있으므로 YES를 출력해주자.

음수 사이클이 없다면 NO를 출력해주면 된다.

 

 

단, 문제에서 지점을 연결하는 도로는 양방향 간선을 의미하지만 웜홀은  단 방향 간선을 의미한 다는 것을 주의하자.

 

코드