[백준] 1719. 택배 - Python

[Gold III]

 

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

1719번: 택배

 

풀이

모든 노드에서 시작하여, 다른 모든 노드로까지의 최단 경로를 구해야 하는 문제이므로,

플로이드-와샬(Floyd-Warshall) 로 풀이할까- 생각했다.

 

그러나 음의 가중치를 가지는 간선이 존재하지 않았고,

플로이드-와샬의 Time Complexity는 O(V^3),

다익스트라로 풀이한다면 O(E*VlogV) 정도이기 때문에, 다익스트라로 풀이하기로 하였다.

 

모든 노드를 하나하나 시작 노드로 잡고 다익스트라를 반복하면 된다.

다만, 역추적을 통해 최단 경로를 지날 때 거치는 노드를 알아야 한다.

이를 다익스트라 알고리즘 내에서, 한 시작 노드에서 - 다른 모든 목적지 노드까지의 최단 경로 내의, 목적지에 도착하기 직전의 노드를 route 배열을 통해 저장하고, 이를 이후 역추적하여 저장한다. (line 26, 42, 46~56)

Ex. 예를 들어, 예제 입력 1에서, 시작 노드를 1로 하는 다익스트라를 진행할 때,

1 -> 6의 최단 경로는 1-2-3-6 이므로, route[6] = 3 이 된다. (1->6의 최단 경로에서, 목적지 도착 직전의 노드가 3)

이런 식으로 모두 계산하게 되면, route 배열은 [-, -, 1, 1, 3, 2, 5] 가 된다.

이를 이용해, 최단 경로 내의 가장 먼저 거쳐야 하는 노드를 구할 수 있다. (다르게 말하면, 최단 경로 내의 두 번째 노드)

목적지가 n일 때, route[n] = (출발 노드) 가 될 때까지 역추적을 한다.

1->6의 경우, route[6] = 5 / route[5] = 2 / route[2] = 1 이므로,

1->6 에서의 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장 은 2이다.

(line 46~56)

 

AC.

import heapq

N, M = map(int, input().split())
graph = {}
# graph 입력
for _ in range(M):
    a, b, t = map(int, input().split())
    if graph.get(a):
        graph[a].append([b, t])
    else:
        graph[a] = [[b, t]]
        
    if graph.get(b):
        graph[b].append([a, t])
    else:
        graph[b] = [[a, t]]

result = [["-"]*(N+1) for _ in range(N+1)]

# i부터 시작하는 다익스트라
for i in range(1, N+1):
    # 최단 시간 기록 배열
    time = [1e9]*(N+1)
    time[i] = 0
    # 최단 경로 도달 루트 저장 (최단 경로에서 목적지에 도착하기 직전의 노드를 저장)
    route = [0]*(N+1)

    q = []
    heapq.heappush(q, (0, i))

    while q:
        t, n = heapq.heappop(q)
        
        # 새로운 경로에 걸리는 시간이 기존 경로보다 오래 걸리면 pass.
        if time[n] < t:
            continue
        
        for now, cost in graph[n]:
            newCost = t + cost
            if newCost < time[now]:
                time[now] = newCost
                route[now] = n
                heapq.heappush(q, (newCost, now))
            
    # i -> j 최단경로의 처음 거치는 노드 추적
    for j in range(1, N+1):
        if i==j:
            continue
        
        now = j
        while result[i][j] == "-":
            # 직전이 시작 노드라면
            if route[now] == i:
                result[i][j] = now
            else:
                now = route[now]
    
for i in range(1, N+1):
    print(*result[i][1:])