[백준][BOJ1865] 웜홀

Algorithm/Bellman-Ford

by bedamino 2021. 8. 3. 23:50

1. 문제 : https://www.acmicpc.net/problem/1865

1865번: 웜홀

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),

www.acmicpc.net

2. 풀이 : Bellman-Ford

3. 설명

'한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우'는 문제에서 주어진 그래프에 음수 싸이클이 존재하는 경우이다. 문제에서 출발 지점을 명시해 주지 않았기 때문에 출발 지점으로 임의의 지점을 선택하여 Bellman-Ford를 수행한 후, 음수 싸이클의 유/무를 판단할 수 있다. 하지만 그림[1]과 같이 단절된 그래프에서 임의의 지점을 잘 못 선택하면 음수 싸이클을 찾을 수 없게 된다.

결국 모든 지점에 대하여 Bellman-Ford를 수행하여 음수 싸이클의 유/무를 판단해야 하는데, 이 경우 N개의 지점이 존재하면 N번의 Bellman-Ford를 수행하게 되고 '시간 초과'로 문제를 풀 수 없게 된다.

Bellman-Ford의 edge relaxation 조건은 다음과 같다.

min[edge.from] != INF && min[edge.to] > min[edge.from] + edge.time

최초 edge relaxation 수행 시, 위의 조건에서 'min[edge.from] != INF' 조건으로 인해 출발 지점에서부터의 최단 시간이 update 되기 전에는 다른 지점에서의 최단 시간은 update 되지 않는다. 즉, 'min[edge.from] != INF' 조건을 삭제함으로써 모든 지점에서의 최단 시간을 update 할 수 있다. 여기서 주의할 점은 'min[edge.from] + edge.time'의 연산 결과로 overflow가 발생하면 음수가 되기 때문에 overflow가 발생하지 않을 적절한 값을 선정하여 INF 값으로 지정한다.

edge relaxation의 조건 변경과 적절한 INF값 설정으로 모든 노드에서의 최단 시간을 update 할 수 있으며, 이때 최단 시간의 값은 정확한 값은 아니지만 문제에서 요구하는 음수 싸이클의 유/무는 정확히 판단할 수 있다.

4. 코드