[백준] 11404 플로이드 (python 파이썬)

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

11404번: 플로이드

플로이드-와샬 알고리즘을 쓰는 문제.

모든 노드 쌍의 최단 거리를 구할 수 있다. 시간 복잡도는 O(N^3)

 

풀이과정

cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            cost[i][j] = 0

for i in range(m):
    a, b, c = map(int,sys.stdin.readline().rstrip().split())
    if cost[a][b] > c:
        cost[a][b] = c

먼저 데이터 전처리를 해준다. 자기자신과의 거리는 0으로 초기화 해주고 나머지는 주어진 입력값을 넣어준다.

문제에서 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 라고 했으므로 노드사이 거리중 최소값을 넣도록 한다.

 

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

플로이드 와샬 알고리즘은 코드로 나타내면 매우 간결하다.

출발점 i, 도착점 j 그리고 중간에 거쳐가는 지점 k 가 있을때, 기존에 있던 최단거리(cost[i][j])와 k를 거쳐가는 최단거리(cost[i][k] + cost[k][j]) 를 비교해서 최소값을 업데이트 해주면 된다.

 

 

전체 코드

import sys
INF = int(1e9)
N = int(input())
m = int(input())
bus = []

cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            cost[i][j] = 0

for i in range(m):
    a, b, c = map(int,sys.stdin.readline().rstrip().split())
    if cost[a][b] > c:
        cost[a][b] = c

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

# print(cost)

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if cost[i][j] == int(1e9):
            print(0, end=' ')
        else:
            print(cost[i][j],end=' ')
    print()