#283 백준 파이썬 [11404] 플로이드 - 플로이드 와샬

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

 

SOLUTION

플로이드 워셜 알고리즘을 사용하는 기초적인 문제다. 각각의 지점에서 모든 정점에 관한 최단 경로를 구하는 알고리즘

위키피디아보다 나무위키에서 보다 잘 설명해주고 있다. 설명 패스 (https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

 

요약하자면 i를 출발해 j로 바로 가는 것보다

i를 출발해 k를 거쳐 j로 가는 게 효율적일 경우(저렴할 경우) 해당 값을 갱신해주는 것이다.

경로 k라 해서 하나의 정점 k만 거치는 것이 아니다. 여러 정점을 거치는 모든 경우의 수가 포함되어 있다.

 

주가 되는 코드는 다음과 같이 표현할 수 있다.

bus_cost[i][j] = min(bus_cost[i][j], bus_cost[i][k] + bus_cost[k][j])

 

3중 포문을 돌아야해서 시간 복잡도는 O(n^3)이다.

주의할 점은 3중 포문 중 경로가 되는 k의 포문이 가장 위에 있어야 누락하지 않고 한번에 돌 수 있다는 것이다.

PYTHON CODE

#입력
n = int(input())
m = int(input())
bus_cost = [[100001 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    start, end, cost = map(int, input().split())
    bus_cost[start][end] = min(cost, bus_cost[start][end])

#플로이드-워셜 알고리즘
for k in range(1, n+1): #경로 for문이 가장 상위 단계여야 누락되지 않는다
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j: #자기 자신으로 오는 경우는 없다고 했으므로
                bus_cost[i][j] = 0 
            else: #경로 거치는 것 or 직접 가는 것 or 이전 경로들
                bus_cost[i][j] = min(bus_cost[i][j],
                                     bus_cost[i][k] + bus_cost[k][j])


#출력
for row in bus_cost[1:]:
    for col in row[1:]:
        if col == 100001:
            print(0, end = " ")
        else:
            print(col, end = " ")
    print()