[백준] 11404번-(Python 파이썬) - Floyd-Warshall

문제링크 : https://www.acmicpc.net/problem/11404

이번 문제는 플로이드-워셜 알고리즘 문제이다.

플로이드 워셜은 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘이다.

1. 하나의 정점에서 다른 정점으로 갈 수 있는 최소비용을 배열에 값을 저장한다. (갈 수 없으면 inf로 배열값 저장)
2. 3중 for문을 통해 거쳐가는 정점을 설정한 후 해당 정점을 거쳐가서 비용이 줄어드는 경우 값을 바꿔준다.
3. 위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색한다.

DP라고도 볼 수도 있으며 코드는 간단하여 설명은 코드에 주석으로 하였다.

import sys

input = sys.stdin.readline
inf = sys.maxsize

n = int(input())
m = int(input())

#최단 경로를 담는 배열
dist = [[inf] * n for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    if dist[a-1][b-1] > c:
        dist[a-1][b-1] = c

for k in range(n):          #거치는 점
    for i in range(n):         #시작 점
        for j in range(n):        #끝 점
                # k를 거쳤을 때 더 적은 경로
            if i != j and dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

for i in dist:
    for j in i:
        if j == inf:
            print(0, end=" ")
        else:
            print(j, end=" ")
    print()