백준 11404 - 플로이드 파이썬

문제

11404번: 플로이드

 

개념(플로이드 워샬)

출처: 위키피디아

위에서 첫 번째 외부 반복문의 반복 이전은 k = 0으로 표시했으며, 이것을 통해 알게 된 경로는 그래프의 한 변에 대응한다.

k = 1일 때, 꼭짓점 1을 통과하는 경로를 찾을 수 있다: 특히, 경로 [2,1,3]을 찾았기 때문에, 변이 더 적지만 더 (가중치의 관점에서)긴 경로인 [2,3]을 대체한다. k = 2일 때, 꼭짓점 {1,2}를 통과하는 경로를 찾았다.

빨간 색과 파란 색의 네모는 경로 [4,2,1,3]이 경로 [4,2]와 이전 반복에서 찾은 [2,1,3]이 2를 교차점으로 결합해서 이루어져 있다는 것을 나타낸다.

경로 [4,2,3]은 2에서 3까지 가는 경로가 [2,1,3]보다 길기 때문에 고려하지 않는다.

k = 3일 때, {1,2,3}을 지나는 경로를 찾는다. 마지막으로, k = 4일 때, 모든 최단경로를 찾게 된다.

 

코드 

'''
n(2 ≤ n ≤ 100)개의 도시가 있다.
그리고 한 도시에서 출발하여 다른 도시에 도착하는
m(1 ≤ m ≤ 100,000)개의 버스가 있다.
각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데
필요한 비용의 최솟값
'''

import sys

# 무한을 의미하는 값으로 10억을 설정
INF = int(1e9)

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

# 도시간의 버스 노선 정보를 입력받아 2차원 리스트로 저장
graph = [[INF] * (n + 1) for _ in range(n + 1)]
m = int(input())  # 버스 노선의 개수
for _ in range(m):
    a, b, c = map(int, input().split())
    # 동일한 도시간의 버스 노선이 여러 개인 경우 최소값으로 저장
    if c < graph[a][b]:
        graph[a][b] = c

# 자기 자신으로 가는 버스 노선은 0으로 초기화
for i in range(1, n + 1):
    graph[i][i] = 0

# 플로이드-와샬 알고리즘 수행
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()

코드 형식이 정형화되어 있어서 

플로이드-워샬이 어렵다고 말을 많이 들었는데 생각보다는 괜찮다