[백준 11780] 플로이드-워셜 알고리즘 - 파이썬(Python)

플로이드 2 

문제

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

출력

먼저, n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

그 다음에는 n×n개의 줄을 출력해야 한다. i×n+j번째 줄에는 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 k를 출력한다. 그 다음, 도시 i에서 도시 j로 가는 경로를 공백으로 구분해 출력한다. 이때, 도시 i와 도시 j도 출력해야 한다. 만약, i에서 j로 갈 수 없는 경우에는 0을 출력한다.

예제 입력 1

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

예제 출력 1

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0
0
2 1 2
2 1 3
2 1 4
3 1 3 5
4 2 4 5 1
0
5 2 4 5 1 3
2 2 4
3 2 4 5
2 3 1
3 3 5 2
0
2 3 4
2 3 5
3 4 5 1
3 4 5 2
4 4 5 1 3
0
2 4 5
2 5 1
2 5 2
3 5 1 3
3 5 2 4
0

---

플로이드-워셜 알고리즘

● 다익스트라( O(ElogV) ) vs 벨만-포드 ( O(EV) ) vs 플로이드-워셜 ( O(V^3) )

다익스트라는 양수엣지에서 가장 빠르게 최단거리를 구하는 알고리즘이고, 벨만-포드는 음수엣지에서 최단거리를 구하는 알고리즘이라면, 플로이드는 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다. (플로이드-워셜 알고리즘은 음의 간선도 사용할 수 있습니다)

 

그러므로 한노드에서 출발하는 최단거리를 구하라고 하면 오래 걸리지만, 출발노드가 계속 달라지면서, 최단거리의 질의가 많아지면 빛을 발하는 알고리즘이라고 볼 수 있습니다.

 

이 문제도 최단거리 문제여서 다익스트라를 떠올릴수 있겠지만, 모든 노드와 모든 노드간의 모든 경우의 수에 대한 최단거리이므로 플로이드워셜을 이용해서 느리지만 한번에 다 구하는것이 옳다고 볼 수 있습니다

 

동적계획법(DP)의 원리를 이용한 알고리즘으로 점화식은 아래와 같습니다.

s에서 시작해서 e로 간다고 하겠습니다. s->k->e 방식으로 k를 경유해서 갈때,

 

D[s][e] = min(D[s][k] + D[k][e] , D[s][e])

 

s->e 로 가는 최단거리중에 k가 있을때, s->e로 가는 최단거리는, s->k로 가는 최단거리와 k->e로 가는 최단거리를 합한것과 같기 때문입니다.

---

1.모든 노드 간의 최단거리를 구해야 하므로 2차원 인접 행렬(DP 테이블)을 구성합니다.

DP테이블에서는 기본적으로 거리가 무한대로 설정해줍니다. 그리고 자신이 자신한테 가는 경로는 0으로 초기화 해줍니다.

노드->노드	1	2	3
1	0	INF	INF
2	INF	0	INF
3	INF	INF	0

 

2. 엣지들을 이용해 DP테이블에 값을 입력합니다.

1->2 로 가는 가중치 3의 엣지와, 3->2 로 가는 가중치 5의 엣지가 있다면 테이블에 입력해줍니다.

노드->노드	1	2	3
1	0	3	INF
2	INF	0	INF
3	INF	5	0

 

3. 1번 노드부터 시작해 각 k를 한번씩 뽑고 k에 대해서 s-k-e 경로를 지정할 s와 e 를 한번씩 뽑아서 점화식을 적용시켜줍니다.

i -> k -> j 로 갈 경로를 이 순서로 삼중 반복문으로 반복해줍니다.

 

for k in range(1,n+1):#경유지
    for i in range(1,n+1):
        for j in range(1,n+1):
            D[i][j] = min(D[i][k] + D[k][j], D[i][j])

---

새로 추가된 구현 - 경로

경유하는 노드들을 리스트로 이차원 배열에 저장시키기로 했습니다.

그리고 아래 점화식을 만들어서 수행해줬습니다.

step[i][j] = step[i][k] + [k] + step[k][j]

 

1->6으로 가는 최단 경로가 1 -> 3 -> 5 -> 6 일때,

경로 배열에는 처음과 끝을 제외한 step[1][6] = [3,5] 가 입력되도록 설정했습니다.

 

DP[1][5] = DP[1][3] + DP[3][5] 과정에서 step[1][5] = step[1][3] + [3] + step[3][5] = [ ] + [3] +[ ] = [3]

DP[1][6] = DP[1][5] + DP[5][6] 과정에서 step[1][6] = step[1][5] + [5] + step[5][6] = [3 ] + [5] + [ ] = [3,5]

위와 같은 방법으로 각 경유한 노드들을 리스트에 들어가도록 설정했습니다.

---

파이썬 코드

앞에 설명한 알고리즘 그래도 적용해 줍니다.

 

1. 문자리스트를 문자열로 합치기

' '.join(['1' , '2' , '3']) = "1 2 3"

 

2. 문자가 아닌(정수등등) 리스트를 문자열로 합치기

' '.join(map(str, [1,2,3])) = "1 2 3"

 

# 플로이드-워셜
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
DP = [[sys.maxsize] * (n+1) for _ in range(n+1)]
step =  [[[] for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1):
    DP[i][i] = 0
for _ in range(m):
    s,e,w = map(int, input().split())
    DP[s][e] = min(w, DP[s][e])

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if DP[i][k] != sys.maxsize and DP[k][j] != sys.maxsize and DP[i][k] + DP[k][j] < DP[i][j]:
                DP[i][j] = DP[i][k] + DP[k][j]
                if i!=j and i!=k and j!=k:
                    step[i][j] = step[i][k] + [k] + step[k][j]

for i in range(1,n+1):
    out = ""
    for j in range(1,n+1):
        if DP[i][j] == sys.maxsize:
            out+="0 "
        else:
            out+= str(DP[i][j]) + ' '
    print(out)

for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j or DP[i][j] == sys.maxsize:
            print(0)
        else:
            # 가는 경로 리스트 = 처음+경유+도착
            way = [i] + step[i][j] + [j]
            print(len(way) , ' '.join(map(str, way)))