[Python/파이썬] 백준 1719번 택배

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

코드

import sys
input = sys.stdin.readline

INF = int(1e9)

n, m = map(int, input().split())
graph = [[INF]*(n+1) for _ in range(n+1)]
path_table = [["-"]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    graph[i][i] = 0

for _ in range(m):
    a, b, t = map(int, input().split())
    graph[a][b] = t
    graph[b][a] = t
    path_table[a][b] = b
    path_table[b][a] = a

for k in range(1, n+1):
    for start in range(1, n+1):
        for end in range(1, n+1):
            if graph[start][end] > graph[start][k]+graph[k][end]:
                graph[start][end] = graph[start][k]+graph[k][end]
                path_table[start][end] = path_table[start][k]

for i in range(1, n+1):
    print(*path_table[i][1:])

 

하나의 정점에서 다른 정점으로 가는 경로표만 구하는 것이 아니라 모든 정점에 대해 구해야 하므로 플로이드 워셜 알고리즘을 사용했다. 

 

2차원 배열 하나는 두 정점 간의 최단거리를 표시하고(`graph`), 다른 하나는 최단 경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 표시한 경로표(`path_table`)이다. 

처음에는 path_table에 입력받은 경로들의 끝점을 표시해놓는다. 만약 1번과 3번을 잇는 경로가 입력으로 들어온다면 path_table[1][3]에는 3, path_table[3][1]에 1을 기록해놓는다. 

그리고 플로이드 워셜 알고리즘을 수행하며 더 짧은 경로를 찾을 때마다 path_table의 값을 앞 경로(start->k)의 path_table[start][k]으로 업데이트하여 start에서 end로 최단경로로 갈 때 처음 방문할 정점을 표시한다.