[Python] 백준 11404 플로이드

1. 문제 링크

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

11404번: 플로이드

 

2. 문제 요약

• a → b로 가는 비용의 최솟값 모두 구하기

3. 아이디어 정리

• 플로이드 와샬. 모든 정점 최단 거리 구하기

참고 - 플로이드 와샬

💡 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용

플로이드 워셜 점화식

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.

• a에서 b로 가는 최단 거리, a에서 k를 거쳐 b로 가는 거리 비교

4. 문제 풀이

4-1. 내 풀이

"""
 모든 a> b로 최소 비용
"""

import sys
INF = int(1e9)

n = int(sys.stdin.readline())  # 도시의 수
m = int(sys.stdin.readline())  # 버스의 수

graph = [[INF] * (n + 1) for _ in range(n + 1)]    # 모든 최단 거리를 저장
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = min(c, graph[a][b])   # 노선이 하나가 아닐 수 있음 > 최소값 넣기 

# 2. 다이나믹 프로그래밍
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

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

 

5. 결론

• 플로이드 와샬