백준 11404번(플로이드)

📒 알고 가야 하는 것

플로이드-와샬 알고리즘
- 모든 정점에서 모든 정점으로 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘은 하나의 정점에서 모든 정점까지의 최단 거리
- but 플로이드-와샬은 '거쳐가는 정점'을 기준으로 한다

📌 코드

import sys

INF = 1000000000
input1 = int(sys.stdin.readline())
input2 = int(sys.stdin.readline())

result = [[INF for i in range(input1)] for j in range(input1)]


for i in range(input2) :
    a, b, c  = map(int, sys.stdin.readline().split())

    if result[a-1][b-1] > c :
        result[a-1][b-1] = c

for k in range(input1) :
    for i in range(input1) :
        for j in range(input1) :
            if i!=j and result[i][j] > result[i][k] + result[k][j] :
                result[i][j] = result[i][k] + result[k][j]

for i in range(input1) :
    for j in range(input1) :
        if result[i][j] == 1000000000 :
            print(0, end = ' ')
        else :
            print(result[i][j], end= ' ')
    print()

📌 피드백

- 플로이드-와샬 알고리즘 그 자체의 문제이며 이 알고리즘만 알고있으면 바로 풀 수 있다.
- 플로이드-와샬 알고리즘에 대해서 잊지 않고 다익스트라 알고리즘 문제가 나왔을 때와 비교해볼 필요가 있음.