[Baekjoon 11404] 플로이드

문제

💛Ⅳ [Baekjoon 11404 - 플로이드]

문제 풀이 방법

모든 도시에 대하여 최단거리를 구해야 한다면 플로이드-워셜 알고리즘을 사용한다!

1. 최단거리를 저장하기 위한 2차원 배열을 INF로 초기화한다.
2. 자기 자신까지의 거리는 0으로 초기화한다.

3. 연결 도로에 대한 정보를 입력받는다.
   이 때, 시작과 도착도시를 연결하는 도로는 하나가 아닐 수도 있다는 조건이 있기 때문에 입력 시 최소 비용만 저장하도록 한다.

4. 모든 그래프의 순회를 n번 반복하면서 A → 현재 노드 → B로 가는 비용을 확인하고 최단 거리를 갱신한다.

풀이 코드

Python

# 플로이드 워셜 알고리즘
import sys
input = sys.stdin.readline

INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _ in range(n+1)] # INF 초기화
for i in range(n+1): # 자기 자신의 0으로 초기화
    graph[i][i] = 0

for _ in range(m):
    a,b,c = list(map(int, input().split()))
    graph[a][b] = min(c, graph[a][b])

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j] == INF:
            print(0, end=" ")
        else:
            print(graph[i][j], end=" ")
    print()