[백준] 11404 플로이드 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/11404
• 🔑 플로이드-워셜 알고리즘 (On³)
  • 🔥 점화식
    • graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    • i → j 로 가는 비용보다
    • i → k 를 거쳐 k → j 로 가는 비용이 더 적은지 확인 (i → k → j)
  • 2차원 리스트(그래프)
    • 행 = 출발지
    • 열 = 도착지
    • graph[행][열] = 비용 (초기 값 INF)
    • ex) 1번 노드에서 2번 노드로 가는 비용이 5 : graph[1][2] = 5
  • 이 문제에서 1로 시작하지 않고 0부터 시작한 이유
    • n(도시 개수)가 1개일 때 인덱스 에러 발생함

 

import sys
input = sys.stdin.readline

n = int(input())    # 도시의 개수
m = int(input())    # 버스의 개수

INF = int(1e9)
graph = [[INF] * (n) for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())     # 출발, 도착, 비용
    if graph[a-1][b-1] > c:                     # 같은 노선이면 비용이 적은 노선으로 저장
        graph[a-1][b-1] = c                     # ex) (1, 4, 1), (1, 4, 2)라면 (1, 4, 1)을 저장

# 플로이드-워셜 알고리즘 점화식
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:              # 자신에서 자신으로 가는 비용은 0
                graph[i][j] = 0
            else:
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] == INF:  # i -> j로 갈 수 없는 경우 0출력
            print(0, end=' ')
        else:
            print(graph[i][j], end=' ')
    print()