[Python Algorithm] Dynamic programming(동적계획법) - 플로이드 워샬 알고리즘

> Dynamic programming(동적계획법) - 플로이드 워샬 알고리즘 : 모든 정점이 모든 정점으로 가는 비용을 구하는 알고리즘 (2차원리스트)

 

 

 

 

 

📖 문제 : 플로이드 워샬 알고리즘

 

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

 

 

 

입력설명

 

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

 

 

 

 

출력설명

 

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

 

 

 

입력예제 1

 

58 126 133 322 241 2 5 13 345 423 457

 

 

 

출력예제 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

 

 

 

 

코드

if __name__ == "__main__":

    n, m = map(int, input().split())
    dis = [[5000]*(n+1) for _ in range(n+1)]
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        dis[a][b] = c

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

    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()

 

 

Point ! ⭐️

• 3번째 for문이 정점별로 최소 비용을 구하는 반복문인데,
  k값(1 ~ n+1) 에 따라서 d[i][j]의 최소비용을 업데이트 시켜가며 구한다.
  만약 k = 1이면, d[i][1] d[1][j] 과 d[i][j]의 값 중 최솟값으로 업데이트한다.  => 정점 1을 지난다는 것.
  k = 3 이면, 1, 2, 3 중에서 사용해가면서 최솟값을 구하는 것 ! 1,2,3 순서가 필수가 아닌 321 213 이 될 수도 123 다 안쓰일 수도 !

 

 

 

 

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이