[백준 11657 🥇] 타임머신

문제

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을 출력한다.

 

문제풀이

import sys
from collections import deque

n,m=map(int, sys.stdin.readline().split(' '))

route=[]
for _ in range(m):
    a,b,c=map(int, sys.stdin.readline().split(' '))
    route.append((a,b,c))

dist=[1e9]*(n+1)
dist[1]=0

for v in range(n):
    for s,e,w in route:
        if dist[s]!=1e9 and dist[e]>dist[s]+w:
            if v==n-1:
                print(-1)
                sys.exit(0)
            dist[e]=dist[s]+w

for d in dist[2:n+1]:
    if d!=1e9:
        print(d)
    else:
        print(-1)

한 정점에서 출발해서 모든 다른 정점에 대한 최단 경로를 탐색할 수 있는 벨만 포드(Bellman-Ford) 알고리즘을 사용했다. 

다익스트라 알고리즘과 달리 음의 가중치를 포함해서 최단 경로를 탐색할 수 있다는 점에서 다익스트라 알고리즘이 아닌 벨만 포드 알고리즘을 사용해야 했다. 

 

(가중치가 있는 그래프의 최단 경로를 탐색하는 알고리즘인 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘의 차이점과 사용해야 하는 경우는 추후 따로 포스팅할 예정이다.)

 

벨만 포드 알고리즘은 음의 사이클이 없고, 정점이 V개인 그래프에서 최단 경로는 많아봐야 V-1개의 간선을 지난다는 생각에서 출발한다. 

따라서, 모든 정점에 대해서 V-1번의 반복을 통해 가능한 모든 경로를 탐색해서 정확한 답을 낸다. (여기서 V-1번 반복을 할 때 이미 한 번 계산된 정점에 대해서만 반복한다. 처음 시작할 때 시작 노드인 1번 노드의 최단 경로를 0으로 초기화해주는 이유이기도 하다.)

 

우선 route 배열에 모든 간선의 정보를 (출발지, 도착지, 가중치) 형태로 저장한다. 

그리고 1번에서 모든 노드로 가는 최단 경로를 저장하는 dist 배열을 1e9로 초기화하고, 출발 노드인 1번 노드의 최단 경로는 0으로 초기화한다.

for v in range(n):
    for s,e,w in route:
        if dist[s]!=1e9 and dist[e]>dist[s]+w:
            if v==n-1:
                print(-1)
                sys.exit(0)
            dist[e]=dist[s]+w

V-1번 반복하면서 모든 간선을 탐색한다. dist[s] 즉, 시작 노드 1번부터 현재 간선이 나타내는 시작점까지의 최단 경로가 한 번 계산된 경우인지 확인하고(dist[s]!=1e9), dist[e] 즉, 시작 노드 1번부터 현재 간선이 나타내는 도착점까지의 최단 경로가 s번 노드를 한 번 거쳐서 e번 노드까지 가는 경로보다 큰 경우에 dist[e] 값을 갱신해준다. 

 

여기서, 음의 사이클을 찾기 위해서 반복을 V-1번 아니라 V번 반복하는데, 여기서 V번째 반복을 할때 값이 갱신되는 경우엔 음의 사이클이 존재한다는 뜻이므로 -1을 출력하고 프로그램을 종료한다. 

 

이렇게 V-1번 모든 간선을 탐색해서 최단 경로를 갱신해주면 시작 노드부터 모든 노드까지 가는 최단 경로를 dist 배열에 저장할 수 있다. 

출력을 해줄 때는 dist값이 1e9인 경우엔 해당 노드로 갈 수 있는 경로가 없다는 뜻이기 때문에 -1을 출력해주고, 그렇지 않은 경우엔  dist 값을 출력해준다.