[백준]11657 타임머신(Python)

https://www.acmicpc.net/problem/11657

11657번: 타임머신

문제 접근

 

음수 간선이 포함된 상황에서 최단 거리를 구하는 경우 다익스트라 알고리즘을 사용할 수 없기에 벨만-포드 알고리즘을 사용한다.

 

1. 출발 노드의 최단 거리를 0으로 초기화

2. 모든 노드에 대해 반복

   모든 간선을 확인하며, 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우 최단 거리 갱신

3. 음수 순환의 존재 여부를 확인 => n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재

4. 출발 노드로부터 모든 노드까지의 최단 거리 결과 제공 

 

=> 시간 복잡도가 O(N*M)으로 다익스트라 알고리즘의 시간 복잡도인 O((E+V)logV) 보다 느림

 

1. 1라운드

• 1 →  2 : dist[2]를 INF에서 4로 갱신 
• 1 →  3 : dist[3]를 INF에서 3으로 갱신
• 2 →  3 : dist[3]은 이미 3으로 갱신되어 있으므로 4-1 = 3이 더 작지 않기 때문에 그대로 둠
• 3 →  1 : dist[1]은 시작 노드이므로 0이며 갱신x 

2. 2라운드

• 1 →  2 : dist[2] = min(4, 0+4) = 4 (변화x)
• 1 →  3 : dist[3] = min(3, 0+3) = 3 (변화x)
• 2 →  3 : dist[3] = min(3, 4-1) = 3 (변화x)
• 3 →  1 : dist[1] = min(0, 3-2) = 0 (변화x, 시작 노드)

3. 3라운드

• 1 →  2 : dist[2] = min(4, 0+4) = 4 (변화x)
• 1 →  3 : dist[3] = min(3, 0+3) = 3 (변화x)
• 2 →  3 : dist[3] = min(3, 4-1) = 3 (변화x)
• 3 →  1 : dist[1] = min(0, 3-2) = 0 (변화x, 시작 노드)

벨만-포드 알고리즘은 최대 n-1 라운드 필요..?

노드의 개수(n): 3
간선의 정보(edges):
1. (1 → 2, 비용: 6)
2. (2 → 3, 비용: 6)
3. (3 → 1, 비용: -15)

1. 1라운드

• 1 → 2: dist[2] = min(INF, 0 + 6) = 6
• 2 → 3: dist[3] = min(INF, 6 + 6) = 12
• 3 → 1: dist[1] = min(0, 12 - 15) = -3 (음의 순환 발생)

3번째 간선이 시작 노드로 돌아오면서 비용 감소 

2. 2라운드

• 1 → 2: dist[2] = min(6, -3 + 6) = 3
• 2 → 3: dist[3] = min(12, 3 + 6) = 9
• 3 → 1: dist[1] = min(-3, 9 - 15) = -6 (음의 순환으로 인한 비용 감소)

이 라운드에서 더 많은 갱신이 발생했고, 특히 시작 노드의 비용이 더욱 감소

3. 3라운드

• 1 → 2: dist[2] = min(3, -6 + 6) = 0
• 2 → 3: dist[3] = min(9, 0 + 6) = 6
• 3 → 1: dist[1] = min(-6, 6 - 15) = -9 (음의 순환으로 인한 계속되는 비용 감소)

코드

import sys

input = sys.stdin.readline
INF = sys.maxsize

def bellman_ford(start):
    dist[start] = 0 # 시작 노드에 대하여 초기화

    # n번의 라운드를 반복
    for i in range(1, n + 1):
        # 매 라운드마다 모든 간선을 확인
        for j in range(m):
            now, next, cost = edges[j][0], edges[j][1], edges[j][2]

            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[now] != INF and dist[next] > dist[now] + cost:
                dist[next] = dist[now] + cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환 존재
                if i == n:
                    return True

    return False


n, m = map(int, input().split())
edges = []
dist = [INF] * (n + 1)  # 최단 거리 테이블을 모두 무한으로 초기화

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

negative_cycle = bellman_ford(1)

if negative_cycle:
    print(-1)
else:
    for i in range(2, n + 1):
        # 도달할 수 없는 경우
        if dist[i] == INF:
            print(-1)
        # 도달 가능한 경우
        else:
            print(dist[i])

 

문제 회고

 

매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는 것과 달리 매번 모든 간선을 확인해야하므로 시간 복잡도가 큰 건 어쩔 수 없다.