[백준11657번] 타임머신 / Python3

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

예제 입력 1

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

예제 출력 1

4
3

예제 입력 2

3 4
1 2 4
1 3 3
2 3 -4
3 1 -2

예제 출력 2

-1

예제 입력 3

3 2
1 2 4
1 2 3

예제 출력 3

3
-1

나의 풀이

해당 문제는 음수의 가중치가 존재하기 때문에 다익스트라가 아닌 벨만-포드 알고리즘을 사용해야되는 문제였다.

벨만-포드 알고리즘은 다익스트라와 같이 시작 노드에서 다른 모든 노드까지의 길이를 모두 추적할 수 있는 알고리즘이다. 우선, 각 노드까지의 거리를 담는 리스트를 만들고 시작노드의 경우 거리를 0으로 나머지 노드에 대해서는 INF로 초기화를 해준다. 그러고나서 시작 노드부터 접근할 수 있는 모든 노드에 대해서 거리를 계산해보고 더 작은 값으로 업데이트 해나가는 것을 V-1번 반복하여 접근 가능한 방법으로 모두 확인해보는 방식으로 동작한다. (V는 노드의 개수)

현재 노드에서 가중치가 제일 작은 것을 찾아가는 다익스트라와는 다르게 벨만-포드는 모든 경우의 수를 따져주기 때문에 속도는 더 느리다. 허나 조금이라도 시간을 줄일 수 있는 방법으로는 V-1번의 반복마다 최소 거리가 변경이 없다면 종료를 시키는 방법이 있고, 거리를 줄이는 데 사용될 수 있는 노드를 별도의 큐로 관리하는 SPFA를 사용하는 방법이 있다.

또한, 음수의 가중치를 갖는다면 음수 사이클이 존재할 수 있다. 음수 사이클이란, 사이클이 생겨 최솟값이 무한대로 작아지는 현상이다. 이를 벨만-포드에서 캐치해낼 수 있다. 앞서 벨만-포드 알고리즘은 V-1 번 반복해야한다고 설명했다. 그러나 V-1번을 반복하고 나서도 (즉, 모든 경로의 경우를 다 따져본 상태)에서도 최솟값이 업데이트되는 경우라면 음수 사이클이 존재한다고 할 수 있다.

마지막으로 중요한 점이 하나있다. 바로 거리를 담는 리스트에서 INF를 갖는 노드에서는 다른 노드로 접근을 하면 안된다는 것이다. 예를 들어 2번 노드의 거리가 INF인데 2번에서 3번으로 가는 경로가 있어서 3번의 거리를 해당 가중치로 업데이트를 한다면 결과에 영향을 미치기때문이다. 구현을 할때 이 부분을 꼭 생각해주어야했다.

코드

# 11657번 타임머신
import sys
INF = sys.maxsize

n, m = map(int, input().split())
distance = [INF] * (n+1)
adj_list = [[] for _ in range(n+1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    adj_list[a].append([b, c])

distance[1] = 0
for i in range(n):
    is_update = False
    for cur in range(1, n+1):
        if distance[cur] == INF:
            continue

        for node, cost in adj_list[cur]:
            if distance[node] > distance[cur] + cost:
                distance[node] = distance[cur] + cost
                is_update = True
    if not is_update:
        break

if is_update:
    print(-1)
else:
    for i in range(2, n+1):
        if distance[i] == INF:
            print(-1)
        else:
            print(distance[i])