[백준] 11404번 플로이드

• 문제 : 백준 11404번 플로이드

• 알고리즘 : 플로이드-와샬 알고리즘

• 알고리즘 설명
  • 모든 노드 간의 최단 거리를 저장하는 리스트를 만듦
  • 각 원소를 돌면서 k를 지나는 거리와 지나지 않는 거리를 비교해 갱신
  • k를 1부터 n까지 증가시키며 bottom-up으로 DP 수행

• 주의할 점
  • 처음 알고리즘을 적용한 리스트가 왜 결과값과 다른지 한참 생각했는데
  • 자기 자신부터 자기 자신까지 가는 거리를 INF로 초기화 했기 때문에
  • 최단 거리를 갱신해 나갈 때 에지를 하나라도 거친 값으로 갱신하기 때문인 것 같다

• 출처 : https://www.acmicpc.net/problem/11404

• 코드

import sys


def init():
    ipt = sys.stdin.readline
    n = int(ipt())
    m = int(ipt())
    edge_list = []
    for _ in range(m):
        s, e, w = map(int, ipt().split())
        edge_list.append((s,e,w))
    return n, edge_list


def floyd_warshall():
    dist_list = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
    for s, e, w in edge_list:
        dist_list[s][e] = min(dist_list[s][e], w)
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dist_list[i][j] = min(dist_list[i][j], dist_list[i][k]+dist_list[k][j])
    return dist_list


n, edge_list = init()
dist_list = floyd_warshall()
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j or dist_list[i][j] == float('inf'):
            print(0, end=' ')
        else:
            print(dist_list[i][j], end=' ')
    print('')