[BOJ] 백준 1719번 문제 풀이 (Python)

1. 문제 풀이

플로이드-워셜 알고리즘을 사용하여 문제를 풀었습니다.

• $graph[a][b]$: a에서 b로 가는 최단 시간
• $node[a][b]$: a에서 b로 가는 최단 시간 경로로 이동하기 위해 가장 먼저 거쳐야하는 집하장

만약 $a$에서 $b$로 갈 때 $k$로 경유해서 가는 것이 더 빠르다면 다음과 같이 갱신했습니다.

• $graph[a][b] = graph[a][k] + graph[k][b]$
• $node[a][b] = node[a][k]$

2. 코드

import sys
INF = int(1e8)
def input(): return sys.stdin.readline().rstrip()

n,m = map(int, input().split())
graph =[[INF] * (n+1) for _ in range(n+1)]
node = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c, = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
    node[a][b] = b
    node[b][a] = a

for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            if graph[a][b] > graph[a][k] + graph[k][b]:
                graph[a][b] = graph[a][k] + graph[k][b]
                node[a][b] = node[a][k]

for i in range(1,n+1):
    node[i][i] = '-'

for array in node[1:]:
    print(*array[1:])