[알고리즘] 동적 계획법 - 프로이드의 최단 경로 코드 (Dynamic Programming - Floyd's Shortest Paths Code)

문제)

Description

교재와 강의자료를 참고하여 Algorithm 3.4/3.5의 구현을 완성하시오.

주어진 방향 가중치 그래프에 대해서 플로이드 알고리즘(3.4)의 결과인 D, P 행렬을 출력하고

최단경로(3.5)를 찾아 출력한다.

단, D 행렬에서 경로가 없는 정점은 INF = 999 로 표시하도록 한다.

#defineINF999

경로를 출력할 때는 출발 정점과 도착 정점도 함께 표시해야 하며,

경로가 존재하지 않는 정점에 대해서는 NONE이라고 표시해야 함에 주의한다.

출발 정점과 도착 정점이 같은 경우에는 출발 정점과 도착 정점을 따로 표시하면 된다.

Input

첫 번째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.

정점의 번호는 1번부터 N번까지로 가정한다.

두 번째 줄부터 M개의 간선의 정보가 주어진다.

각 간선의 정보 u v w는 각각 간선의 출발 정점 u, 도착 정점 v, 해당 간선의 가중치 w로 주어진다.

모든 간선의 정보가 주어진 후에 다음 줄에 출발/도착 정점의 쌍의 개수 T가 주어진다.

그 다음 줄부터 T개의 출발/도착 정점의 쌍이 주어진다.

Output

먼저, N * N 행렬 D를 출력한다.

다음에 N * N 행렬 P를 출력한다.

D와 P는 floyd2() 함수의 결과값이다.

D와 P 행렬의 출력 이후로 T 개의 최단 경로를 출력한다.

최단 경로는 출발 정점에서 시작하여 중간 정점을 모두 출력하고 도착 정점을 출력한다.

만약 출발 정점에서 도착 정점으로의 경로가 존재하지 않으면 NONE 이라고 출력한다.

Sample Input 1

5 10
1 2 1
1 4 1
1 5 5
2 1 9
2 3 3
2 4 2
3 4 4
4 3 2
4 5 3
5 1 3
25
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
3 1
3 2
3 3
3 4
3 5
4 1
4 2
4 3
4 4
4 5
5 1
5 2
5 3
5 4
5 5

Sample Output 1

0 1 3 1 4
8 0 3 2 5
10 11 0 4 7
6 7 2 0 3
3 4 6 4 0
0 0 4 0 4
5 0 0 0 4
5 5 0 0 4
5 5 0 0 0
0 1 4 1 0
1 1
1 2
1 4 3
1 4
1 4 5
2 4 5 1
2 2
2 3
2 4
2 4 5
3 4 5 1
3 4 5 1 2
3 3
3 4
3 4 5
4 5 1
4 5 1 2
4 3
4 4
4 5
5 1
5 1 2
5 1 4 3
5 1 4
5 5

Sample Input 2

5 8
1 2 7
1 3 4
1 4 6
1 5 1
3 2 2
3 4 5
4 2 3
5 4 1
25
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
3 1
3 2
3 3
3 4
3 5
4 1
4 2
4 3
4 4
4 5
5 1
5 2
5 3
5 4
5 5

Sample Output 2

0 5 4 2 1
999 0 999 999 999
999 2 0 5 999
999 3 999 0 999
999 4 999 1 0
0 5 0 5 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 4 0 0 0
1 1
1 5 4 2
1 3
1 5 4
1 5
NONE
2 2
NONE
NONE
NONE
NONE
3 2
3 3
3 4
NONE
NONE
4 2
NONE
4 4
NONE
NONE
5 4 2
NONE
5 4
5 5

코드, Python)

import sys
input = sys.stdin.readline


def floyd(D, P, n):
    # 최적의 경로를 찾는 함수, D는 최단 경로를 저장하는 배열이고, n은 vertex의 개수
    for k in range(1, n):
        for i in range(1, n):
            for j in range(1, n):
                if D[i][j] > D[i][k] + D[k][j]:     # 기존의 값이 K를 경유하는 값보다 크면 교체함
                    D[i][j] = D[i][k] + D[k][j]
                    P[i][j] = k


def path(P, p, i, j):
    # 경로를 찾는 함수
    k = P[i][j]
    if k != 0:        # P[i][j]는 i에서 j로 가기 전에 마지막으로 들리는 vertex
        path(P, p, i, k)     # 따라서 경로를 알기 위해서는 P[i][P[i][j]]를 또 다시 해야한다.
        p.append(k)
        path(P, p, k, j)


INF = 999       # 경로가 없는 경우를 대비해서 INF를 선언함

ver_num, edge_num = list(map(int, input().split()))       # 정점과 간선의 개수를 입력받음
ver_num += 1      # 범위가 1부터 시작함

W = [[INF] * ver_num for _ in range(ver_num)]       # 초기의 가중치를 저장하는 행렬

for _ in range(edge_num):       # i와 j와 weight를 입력 받아서 저장함
    i, j, weight = list(map(int, input().split()))
    W[i][j] = weight

for i in range(ver_num):        # 자기 자신에게 가는 경로는 0임
    W[i][i] = 0


D = W.copy()        # W를 복사하여 D에다가 저장함
P = [[0] * ver_num for _ in range(ver_num)]     # 경유지를 저장하는 배열

floyd(D, P, ver_num)		# floyd 함수를 호출함

for i in range(1, ver_num):     # D를 출력함
    for j in range(1, ver_num):
        print(D[i][j], end=' ')
    print()
for i in range(1, ver_num):     # Path를 출력함
    for j in range(1, ver_num):
        print(P[i][j], end=' ')
    print()


n = int(input())        # 경로를 출력하기 위해 받는 경우의 수
p = list()      # 경로를 저장하는 리스트
for _ in range(n):
    i, j = list(map(int, input().split()))
    if D[i][j] == INF:
        print('None')
        continue
    p.clear()
    p.append(i)
    path(P, p, i, j)
    p.append(j)
    print(*p, sep=' ')