[python]1104번 플로이드,반복문에서 K 순서가 바깥쪽에 있는 이유

 

처음에는 플로이드 워셜 알고리즘을 모르는 상태에서 문제를 풀어보았다.

문제의 제한사항이나, 입력제한이 널널해서 그런지 

다익스트라 여러번 돌려도 문제를 맞출 수 있었다.

import sys
from heapq import heappush,heappop
input = sys.stdin.readline
city = int(input().strip())
bus = int(input().strip())
graph = [[0 for i in range(city+1)] for j in range(city+1)] #간선의 정보들 저장
for i in range(bus):
    fst,scd,thd = map(int,input().split())
    if not graph[fst][scd]:
        graph[fst][scd] = thd
    else: #가중치가 더 적은 간선 저장
        if graph[fst][scd]>thd:
            graph[fst][scd] = thd
def fw(start):
    dis = [1e9 for i in range(city+1)]
    dis[start] = 0
    que = [(0,start)]
    while que:
        curlen,curx = heappop(que)
        for i in range(1,city+1):
            if graph[curx][i]:
                if dis[i]>curlen+graph[curx][i]:
                    dis[i]=curlen+graph[curx][i]
                    heappush(que,(dis[i],i))
    return dis
for i in range(1,city+1): #1번 노드부터 다익스트라 시작점으로 거리 계산하기
    rst = fw(i)[1:]
    for j in range(city):
        if rst[j] == 1e9:
            rst[j]= 0
    print(*rst) #그때마다 출력

 

 

그러나 효율성을 생각해서 플로이드 워셜알고리즘이 적용된 문제 풀이도 찾아보게 되었다.

인덱싱이 상당히 직관적으로 구현되어 있었다.

 

fmti0720님의 풀이

import sys
input = sys.stdin.readline
INF = sys.maxsize

n = int(input())
m = int(input())
rs = [[INF] *(n+1) for _ in range(n+1)]

for i in range(1, n+1):
    rs[i][i] = 0

for i in range(m):
    a,b,c = map(int, input().split())
    rs[a][b] = min(rs[a][b], c)

for k in range(1, n+1): # 거치는 값
    for j in range(1, n+1): # 시작
        for i in range(1, n+1): # 도착
            if rs[j][i] > rs[j][k] + rs[k][i]:
                rs[j][i] = rs[j][k] + rs[k][i]

for j in range(1, n+1):
    for i in range(1, n+1):
        if rs[j][i] == INF: print(0, end=' ')
        else: print(rs[j][i], end = ' ')
    print()

 

다시 풀어보니 왜 중간지점(거치는 값)이 바깥쪽에 와야하는지 한참을 고민했다.

결국 다른 사람 블로그를 찾아보니

https://scieneer.tistory.com/19

플로이드 와샬 (Floyd - Warshall)

중간지점 거치는 값은 중간지점을 지난 갯수로도 해석이 될 수 있다는 것이었다!

그래서 같은 중간지점 갯수를 지난 노드와 비교를 해야 옳바르게 비교가 가능하다는 것이었다.

중간지점 값이 커질 수록 그 작은 중간지점을 거친 값은 이미 반영되어 있다.