백준 11657번 : 타임머신 in Python
이 문제는 이전의 최단 경로 문제와 유사하나 경로의 가중치가 음수가 될 수 있다는 점에서 약간 차이가 있다.
하지만, 이로 인해 이 문제를 Dijkstra 알고리즘을 이용해 풀 수 없다. 왜냐하면 특정 간선들로 인해 음의 사이클(cycle), 즉 간선들을 반복적으로 지나갈 수록 경로들의 총 가중치가 지속적으로 감소하는 현상이 발생하기 때문이다. 이 때문에 Dijkstra 알고리즘에서 최단 경로를 구하려고 하면 계속 음의 사이클을 돌게 되면서 결국 최단 경로를 찾지 못하는 경우가 발생한다.
이를 방지하기 위해 Bellman-Ford 알고리즘을 이용한다. 이 알고리즘은 Dijkstra와는 달리 우선 모든 정점들에 대해 그 정점들과 인접한 점들에 relax를 한다. 이를 한 번 했을 때 출발점과 인접한 점들까지의 최단 경로를 구할 수 있다. 이후 위 과정을 한 번 더 하면 출발점에서 앞의 인접한 점들과 인접한 점들까지의 최단 경로를 구할 수 있다. 점의 개수가 N개인 그래프 내에서 path의 길이는 기껏해야 N-1이므로 이 과정을 N-1번 반복하면 출발점에서 도달할 수 있는 모든 점들까지의 최단 경로를 구할 수 있다.
그러나 이는 음의 사이클이 발생하지 않았을 때의 이야기이다. 만약 음의 사이클이 있는 경우, 이 과정을 N-1번 반복했을 때 일부 점들은 계속 relax를 한 상황일 것이다. 그러므로 위의 과정을 한 번 더 한다. 즉, 모든 정점들에 대해 그 정점들과 인접한 점들에 대해 relax를 한다. 만약 음의 사이클이 없다면 모든 정점들은 이미 relax를 거쳤으므로 더 이상 relax를 하지 않으려 할 것이다. 하지만 음의 사이클이 존재한다면 이 과정에서도 relax를 할 것이고, 따라서 이 경우는 제대로 된 최단 경로를 구할 수 없다고 판단한다.
이를 코드로 구현할 때는 BellmanFord라는 함수에서 위 과정을 구현하되 만약 가장 바깥쪽 loop의 N번째 순회에서 relax를 실행할 경우 True를 최단 경로 배열과 함께 반환하고, 그렇지 않은 경우 False를 최단 경로 배열과 함꼐 반환한다. 이후 boolean 값이 True면 -1을 출력하고, 그렇지 않은 경우 각 정점들에 대한 최단 경로의 길이를 출력한다. 물론, 최단 경로가 없는 경우 -1을 출력한다.
이를 코드로 구현하면 다음과 같다.
import sys
import heapq
# Bellman-Ford 구현 함수로, v는 시작점을 의미한다.
def BellmanFord(v):
global N
# 최단 경로의 길이를 저장하기 위한 배열
bellman = [sys.maxsize for _ in range(N+1)]
bellman[v] = 0
# 모든 점들에 대해 최단 경로의 길이를 구할 수 있도록 N-1번 반복하고,
# 마지막 N번째 순회는 relax가 여전히 발생하는지 확인한다.
for repeat in range(N):
for i in range(1, N+1):
for [j, k] in graph[i]:
# 마지막 순회에서 relax 발생 여부를 따질 때 최단 경로를 구하지 못한 정점은 무시한다.
if bellman[i] != sys.maxsize and bellman[j] > bellman[i] + k:
bellman[j] = bellman[i] + k
# 마지막 순회에서 relax가 발생한 경우
if repeat == N-1:
return True, bellman
return False, bellman
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
A, B, C = map(int, input().split())
graph[A].append([B, C])
TimeError, bellman = BellmanFord(1)
if TimeError == True:
print(-1)
else:
for i in range(2, N+1):
if bellman[i] == sys.maxsize:
print(-1)
else:
print(bellman[i])