[Python/BOJ] 백준11404 플로이드_플로이드와샬

 

 

 

 

 

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

11404번: 플로이드

 

 

이전에 했던 다익스트라는 한 노드에서 모든 노드로의 정점을 찾는 방법이었다.

이와 비슷한 플로이드 와샬은 모든 노드에서 모든 노드로의 최단 경로를 찾는 알고리즘이다.

 

 

2차원 테이블에 dp를 이용해 최단거리 정보를 저장하며 구한다.

시간복잡도는 O(n^3)로 오래걸린다. 삼중 for문을 사용하기 때문이다.

노드나 간선의 개수가 많으면 플로이드 와샬이 아닌 다익스트라를 고려해보시라

 

 

 

아무래도 dp이기 때문에 점화식이 존재한다. 

 

 

 

a에서 b로 가는 경로는  [  원래 값 (a-b)과 k를 거쳐서 (a에서 k + k에서 b)로 가는 경로]를 비교하여 작은 값으로 갱신한다. 

 

 

 

 

정답 코드 : 

 

if __name__=="__main__" :
    n = int(input())
    m = int(input())
    graph = [[int(1e9)]*(n+1) for _ in range(n+1)]
    # 나 자신은 0 
    for i in range(n+1) :
        graph[i][i] = 0
        
   # 경로가 여러개 들어돌 수 있으므로 min을 달아줘야함  
    for i in range(m) :
        a,b,c = map(int,input().split())
        graph[a][b] = min(c,graph[a][b]) 
    
    # 점화식 수행 
    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]!=int(1e9)) : print(graph[i][j],end=' ')
            else : print(0,end=' ')                           
                
        print()

 

 

주의할 점은 경로가 여러개 들어올 수 있으므로 min을 이용해서 받은 경로의 값 중 작은 값을 사용해야 한다. 

 

 

 

 

 

 

 

 

 

 

 

 

참고 자료 :

https://www.youtube.com/watch?v=hw-SvAR3Zqg 

https://ryu-e.tistory.com/106

[Python] 백준 11404 플로이드