[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 11

Chooooo·2023년 2월 15일

파이썬 알고리즘 문제풀이

목록 보기

72/72

플로이드 워샬 알고리즘

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

import sys
sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline

n,m = map(int, input().split()) #노드, 간선
INF = 24242424
dis = [[INF] * (n+1) for _ in range(n+1)] #dp 테이블을 dis이름으로. 최단거리 구하는거니깐.
for i in range(1,n+1):
    dis[i][i] = 0 #자기 자신으로 가는 것은 0

#각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    a,b,c = map(int, input().split())  #이건 직행하는 간선 값.
    dis[a][b] = c

#점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1,n+1): #k는 거쳐가는 노드
    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] == INF:
            print("M", end = " ")
        else:
            print(dis[i][j], end = " ")
    print()

😀 코멘트

그래프에서 모든 정점에서 모든 정점으로 가는 최단거리. 그 최소 비용을 구하는 것이다.

1번 정점에서 다른 정점들로 가는 최단거리를 구하고, 또 2번 정점에서 다른 정점들고 가는 최단거리 구하고, 등등 끝까지 도는 것이다.
이렇게 생각하면 플로이드 워셜의 dp 테이블은 2차원 리스트이다.

🚀 플로이드 워셜도 냅색 알고리즘과 동일한 원리이다.

😀 dis[i][j]는 i정점에서 j정점으로 가는데 드는 최소비용 값을 저장한다. (i가 출발 정점, j가 도착 정점)

일단 dp테이블에 한번의 간선으로 갈 수 있는 값들(직관적. 자명하게 알 수 있는 값)을 미리 초기화 하고 진행하자. (즉 이 값들이 인접행렬 초기값이야)
처음 dp 테이블에 저장된 값들은 한번에 갈 수 있는 값들만 저장되어 있는 것이다.

🚀 이제 기존 값(i → j로 가는 기존 값)과 중간에 노드를 거쳐서(몇개를 거치든) 가는 값 중에 최소 값을 택할 것이다.

i → j로 갈 때 1~N까지의 노드가 몇개든 존재할 수 있다.
이 사이에 존재하는 노드들은 1,2,3이 꼭 있다면 1→2→3 순이 아니라 2→1→3 처럼 될 수도 있다.

🏈 위 내용을 이해하는 것이 매우 중요한데, 예를 들어 k == 3을 적용하고 있는 2중 포문을 돌고 있다고 생각하면 dis[5][4]의 값은 (dis[5][3] + dis[3][4]) 이렇게 가는 방법이 존재할 수도 있다.

k가 3을 적용하고 있다는 것은 dp 테이블이 k = 1,2를 거쳐서 가는 것까지 적용된 테이블 값일거야. 그렇다면 dis[5][3]의 값이 5 → 2 → 3으로 가는 값이 최단거리 일 수 있고, dis[3][4]의 값은 3 → 1 → 4의 값이 최단거리 일 수도 있다.
그렇다면 dis[5][4]의 값은 5 → 2 → 3 → 1 → 4 순으로 가는 것이 최단거리라는 것인데, k는 이미 1,2를 거쳐왔고 k는 현재 3이다. 다시 말해 꼭 1→2→3순으로 되는 것이 아니라는 거야!
결국 전체를 다 돌면 모든 노드에서 모든 노드까지의 최단거리를 다 알 수 있게 된다는 뜻 !

Chooooo

back-end, 지속 성장 가능한 개발자를 향하여

이전 포스트

[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 11