백준 11404플로이드

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

11404번: 플로이드

내 기억상 유튜브에서 보고 처음으로 감탄사를 내뱉었던 알고리즘

 

우리는 n*n 배열을 만들거다.

배열 i,j는 i에서 j로가는 최소 경로이다.

직접가는 버스가 있으면 가중치를, 없으면 존나큰값을 넣는다.

 

n에 대한 3중 반복문을 돌면서,

arr[i][j]가arr[i][k]+arr[k][j] 즉  직접가는 경로보다 k지점을 거쳐서 가는 경로가 빠르다면,

더 빠른 경로를 업데이트해준다.

이게다다.

 

##플로이드알고리즘!!!
import sys
input=sys.stdin.readline


n=int(input())
bus=int(input())
##arr[i][j]는 i에서j로 가는 최소비용 
arr=[[0 if i==j else 1e+8 for i in range(n)]for j in range(n)]

# 0은 제외니 -1해주기
for _ in range(bus):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    arr[a][b]=min(arr[a][b],c)


#여기까지 arr완성

#플로이드알고리즘
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:continue
            if arr[i][j]>arr[i][k]+arr[k][j]:
                arr[i][j]=arr[i][k]+arr[k][j]

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

p.s

알고리즘에 대해서 한참 고민했던것이, i,j가 아직 업데이트되지 않았을때의 경로가 최소경로일 경우를 못구할 것 같았다.

하지만, 쓸데없는 걱정이였다.

배열에는 이미 이전 모든k를 거쳤을때의 최솟값이 업데이트되어있을것이다.

k를 두번 거칠 일은 절대 없으므로(상식상)

반복문이종료된 후에는 모든 값이 최소경로를 나타내게 된다!!