백준 - 11404번(플로이드)

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

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

arr = [[float('INF') for _ in range(n)] for _ in range(n)]
bus = []

for i in range(n):
    arr[i][i] = 0

for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    if arr[a-1][b-1] > c:
        arr[a-1][b-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if arr[i][j] > arr[i][k] + arr[k][j]:
                arr[i][j] = arr[i][k] + arr[k][j]

for i in range(n):
    for j in range(n):
        if arr[i][j] == float('INF'):
            arr[i][j] = 0
        
for i in arr:
    print(*i)

 

플로이드 와샬 알고리즘의 가장 기본적인 문제다.

3중 반복문을 이용해서 각 이동 경로마다 최적의 값을 찾는다.

map의 크기가 아주 크지 않다면 코드가 간결한 것이 장점이다.

문제 조건에 맞게 float('INF')를 0으로 바꾸는 것을 주의해야 한다.