[Python/파이썬] 백준 알고리즘 11657번 - 타임머신 (벨만 포드 알고리즘/Bellman-Ford)

 

 

 

<풀이>

"""
1. 아이디어
- 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간 -> 다익스트라

2. 시간 복잡도
- O(ElgV) : 6000 * lg(500) ~= 16000     -> 가능

3. 변수
- N, M : int
- 인접 리스트 : (이동 시간, 도착 도시)[][]
- 최단 거리 배열 : int[]
- 갈 수 있는 도시들 : heap
"""
import sys
import heapq
INF = sys.maxsize

input = sys.stdin.readline

N, M = map(int, input().split())

edge = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    edge[A].append([C, B])

heap = [[0, 1]]
dist = [INF] * (N + 1)
dist[1] = 0

is_loop = False

while heap:
    if is_loop: break
    w, v = heapq.heappop(heap)
    if w != dist[v]: continue
    for nw, nv in edge[v]:
        if dist[nv] > dist[v] + nw:
            dist[nv] = dist[v] + nw
            if dist[nv] < -5000000:
                is_loop = True
                break
            heapq.heappush(heap, [dist[nv], nv])

if is_loop:
    print(-1)
else:
    print('\n'.join(map(lambda x: str(x) if x < INF - 1 else '-1', dist[2:])))

처음에는 자주 풀던 다익스트라 문제의 단순 변형일 것이라 생각했다.

간선의 최소 비용이 -10,000이고 최대 노드 개수가 500개이므로 한 없이 음의 무한대로 나갈 수 있는 사이클이 발생하지 않는 한 얻을 수 있는 최소 비용은 -5,000,000이라고 생각했다.

문제는 위 해결법대로 제출 했을 때 시간초과가 발생했다.

이는 당연한 것이었는데, -5,000,000에 도달할 때까지 수많은 노드 방문을 할테니 제한 시간을 초과하는 것이었다.

 

이후 이 문제를 해결할 수 있는 벨만 포드 알고리즘을 알게 되었다.

 

음의 간선이 포함된 경우에도 다익스트라로 풀 수 있지만, 음수 간선의 순환이 포함되어 있다면 다익스트라 알고리즘을 사용할 수 없다.

 

이때 사용할 수 있는 것이 벨만 포드 알고리즘이다.

 

벨만 포드 알고리즘을 간단하게 설명하면 전체 간선을 하나씩 확인하며 해당 간선을 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 N번 반복하는 알고리즘이다.

이 때 마지막 N번 반복 때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재함을 알 수 있다.

 

즉, 다익스트라 알고리즘이 heap 자료구조를 활용해 최단 거리가 가장 짧은 노드를 선택하는 방식으로 진행됐다면,

벨만 포드 알고리즘은 매번 모든 간선을 전부 확인하는 방식으로 진행된다.

 

따라서 벨만 포드 알고리즘은 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다.

또 시간 복잡도는 O(VE)이다. (노드 개수만큼의 라운드동안 각각 모든 간선을 확인하므로)

 

 

새로 알게된 벨만 포드 알고리즘을 이용해 풀면 아래와 같다.

"""
1. 아이디어
- 음의 순환이 발생할 수 있기 때문에 다익스트라 알고리즘으로는 풀 수 없다.
    - 벨만 포드 알고리즘 활용

2. 시간 복잡도
- O(VE) : 500 * 6000 = 3,000,000        -> 가능

3. 변수
- N, M : int
- edges : int[][]
"""
import sys
INF = sys.maxsize

input = sys.stdin.readline

N, M = map(int, input().split())

edges = []
for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append([A, B, C])

dist = [INF] * (N + 1)
dist[1] = 0

is_negative_cycle = False

for i in range(N):
    for edge in edges:
        cur_city, arr_city, time = edge
        if dist[cur_city] != INF and dist[arr_city] > dist[cur_city] + time:
            dist[arr_city] = dist[cur_city] + time
            if i == N - 1:
                is_negative_cycle = True
                break

if is_negative_cycle:
    print(-1)
else:
    print('\n'.join(map(lambda x: str(x) if x < INF - 1 else '-1', dist[2:])))

어차피 모든 간선을 조회할 것이므로 인접 간선 리스트를 따로 만들지 않고 그냥 리스트에 때려 넣어도 된다.

그리고 이중 포문을 돌면서(O(VE)) 각 라운드에 모든 간선을 조회하고 다익스트라 때와 유사하게 현재 저장된 도착 도시까지의 최단 시간과 현재 도시 + 이동 시간을 비교해 더 짧은 값으로 교체하는 과정을 넣는다.

이렇게 N - 1 번의 라운드를 진행하고, 마지막 N번째 라운드에서마저 최단 거리 테이블이 갱신되면 음수 간선의 순환이 포함되어 있다고 판단하고 is_negative_cycle 을 True로 바꾸는 것이다.

 

한번의 라운드 동안 최단 거리를 갱신하기 위해 이용할 수 있는 간선의 수는 최소 1개 이상이다.

즉, N-1 라운드를 진행하면 1번 노드에서 특정 노드까지 다른 모든 노드를 거쳐서 갔더라도 최단 거리가 구해져야한다. (최단 거리 제약 한계에 도달했으므로)

하지만 N 번째 라운드에서 갱신이 됐다면 음수 간선의 순환이 있다는 뜻이므로 -1을 출력해주는 것이다.

 

 

 

<핵심 정리>

1. 음수 간선 순환이 존재한다면 다익스트라 알고리즘으론 풀 수없고 벨만 포드 알고리즘을 이용해야한다.

2. 벨만 포드 알고리즘은 다익스트라 알고리즘보다는 시간 복잡도가 높지만 음수 간선 순환 여부를 알 수 있다는 장점이 있다.

3. 벨만 포드 알고리즘의 시간 복잡도는 O(VE)이다.