파이썬 알고리즘-82 (DP) 플로이드-와샬 알고리즘

82.플로이드 워샬 알고리즘
N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에는 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고, M줄에 걸쳐 도로정보와 비용(20 이하의 자연수)이 주어진다. 만약 1번 도시와 2번도시가 연결되고 그 비용이 13이면 “1 2 13”으로 주어진다.

▣ 출력설명
모든 도시에서 모든 도시로 이동하는데 드는 최소 비용을 아래와 같이 출력한다. 자기자신으로 가는 비용은 0입니다. i번 정점에서 j번 정점으로 갈 수 없을 때는 비용을 “M"으로 출력합니다.

▣ 입력예제 1
5 8
1 2 6
1 3 3
3 2 2
2 4 1
2 5 13
3 4 5
4 2 3
4 5 7

▣ 출력예제 1
0 5 3 6 13 //1번 정점에서 2번정점으로 5, 1에서 3번 정점으로 3, 1에서 4번 정점으로 6......
M 0 M 1 8 //2번 정점에서 1번 정점으로는 갈수 없으므로 “M", .......
M 2 0 3 10
M 3 M 0 7
M M M M 0

내 코드

INF=int(1e10)
n,m=map(int,input().split())
dy=[[0]*n for _ in range(n)]
# 답을 구할 테이블 초기화 1
for i in range(m):
    a,b,c=map(int,input().split())
    dy[a-1][b-1]=c
# 답을 구할 테이블 초기화 2
for i in range(n):
    for j in range(n):
        if i!=j and dy[i][j]==0:
            dy[i][j]=INF
# 핵심. k번 노드를 거쳐가는 모든 경우를 모두 구한다.
for k in range(n):
    for i in range(n):
        for j in range(n):
            # i->k->j로 가는 방법과 i->j로 가는 방법 중 최단거리로 갱신
            # i->j도 이전에 k가 돌면서 바뀐 값일 수도 있다
            dy[i][j]=min(dy[i][j], dy[i][k]+dy[k][j])
            
for i in range(n):
    for j in range(n):
        if dy[i][j]==INF:
            dy[i][j]='M'
        print(dy[i][j], end=' ')
    print()

애초에 못 풀 것 같아서 이론을 좀 보고 풀려고 했는데 거의 베끼다시피 해서 의미가 없었다.

풀이

if __name__=="__main__":
    n, m=map(int, input().split())
    dis=[[5000]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        dis[i][i]=0
    for i in range(m):
        a, b, c=map(int, input().split())
        dis[a][b]=c
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j])
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dis[i][j]==5000:
                print("M", end=' ')
            else:
                print(dis[i][j], end=' ')
        print()

반성점

배운 것

• 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다. 이 알고리즘의 핵심은 '거쳐가는 정점'을 기준으로 최단거리를 구하는 것이다. 그래서 거쳐가는 정점을 반복문의 가장 위에 두고 그 아래에서 모든 격자를 한번씩 도는 식으로 구하는 것이다.
  또한 거쳐가는 정점이 바뀔 때 최단거리가 기존 거리보다 짧다면 짧은 값으로 갱신한다는 점에서 DP의 한 종류이다.
  자세한 이론과 설명은 다익스트라 알고리즘과 함께 별도의 포스팅을 하고자 한다.