백준 11404 플로이드 문제풀이

문제 

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

11404번: 플로이드

 

 

 

문제 접근 방식

모든 쌍노드에서 모든 쌍으로 가는 최단 경로를 구해야하기 때문에 플로이드 워셜 알고리즘을 사용하기로 결정.

플로이드 워셜 알고리즘은 DP 알고리즘으로 구현하며 점화식 정의는 아래와 같다.

 

dist[ i ][ j ] = i 번째에서 j 번째로 가는 최단 경로의 길이

 

이때 i 와 j 노드 사이의 노드 k 를 기준으로, k 를 경유해서 가는 경로와 그렇지 않은 경로로 식을 세울 있다.

 

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

 

위의 점화식에 k,i,j 를 순회하면서 dist를 갱신해주면 모든 쌍에서 모든 쌍으로의 최단경로를 구할 수 있다.

 

 

시간 복잡도

코드 내에서 가장 많은 시간 복잡도를 가지는 것이 삼중 for 문이기 때문에 O(n^3) 이 걸리며, n의 최댓값이 100이하이므로 시간내에 동작함을 알 수 있다.

 

 

코드

import sys

input=sys.stdin.readline
print=sys.stdout.write
INF=int(1e7)
MAX=int(1e5)

if __name__=='__main__':
    n=int(input())
    m=int(input())

    #인접 행렬 선언 및 초기화
    adj=[[INF for _ in range(n+1)] for _ in range(n+1)]

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

    #adj[i][j] 을 최단거리로 활용
    #adj[i][j] = i에서 j로 갈 수 있는 최단 경로 길이
    # 자기 자신으로의 최단 거리는 0 이므로 초기화
    for i in range(1,n+1):
        adj[i][i]=0

    # 특정 노드 k 를 기준으로 생각했을 때,
    # k 를 반드시 거치는 경우 vs k 를 거치지 않는 경우
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])
    
    # 최단 경로 adj를 출력
    for i in range(1,n+1):
        print(' '.join(map(str,adj[i][1:]))+'\n')

 

 

회고

전체적으로 어떻게 돌아가는지 흐름은 알겠는데, 어떻게 정당성을 보장하는지 공부가 필요하다..