반응형

문제

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

나의 풀이

해당 문제는 출력 부분을 이해하는데 시간이 좀 걸리는 문제였습니다... 이해한바로 조금 더 쉽게 풀어보자면 처음에 플로이드-와샬을 사용해 구한 dp 배열을 출력해주고 그 다음줄부터는 (i, j)순으로 (1, 1), (1, 2), (1, 3) ... (N, N-1), (N, N)의 최단 경로를 출력하는 문제였습니다.

플로이드-와샬을 구현할 줄 안다면, dp배열을 구하는 것까지는 쉽게 할 수 있겠지만 이 문제의 핵심으로는 플로이드-와샬을 사용하면서 최소 비용에 대한 경로를 구하는 것이었습니다.

필자가 경로를 구한 방법은 다음과 같습니다. 우선, 각 (i, j)에 대하여 최소 비용으로 업데이트가 이루어지는 k의 값을 저장해두는 배열을 만들어주어야 합니다. 즉, i -> j를 갈 때 최소비용이 되는 k에 대한 값을 저장하는 것입니다.

플로이드-와샬 알고리즘의 핵심은 i->j로 갈때 k를 거쳐 지나가는 경우를 따져주며 최솟값을 구하게 됩니다. 즉, i에서 j로 가는 중간 경로를 구하기 위해서는 이 k를 구하는 것과 같은 것입니다. 이렇게 문제를 쪼개면서 접근하다보면 다음과 같은 재귀 알고리즘을 생각해낼 수 있습니다. 예를들어, i에서 j로 갈때 k를 거쳐갈 때가 최소비용이라면 i -> k로 가는 최소 비용 경로와 k -> j로 가는 최소 비용 경로를 합해주면 곧 그것이 i -> j로 가는 최소 비용 경로가 되는 것입니다.

위의 예시를 좀 더 자세히 살펴보면 다음과 같습니다.

왼쪽의 배열은 위에서 말한 i -> j로 갈때 최소비용에 해당하는 k를 담은 배열입니다. 이를 활용해서 오른쪽의 재귀를 따라가보면 최소 비용에 대한 경로를 구하는 방법에 대해 이해를 할 수 있습니다. 말로 설명을 해보면, 2->1로 가는 최소 비용 경로를 구하고자 할 때, trace[2][1]=5k가 5라는 것을 알 수 있습니다. 그렇다고 경로가 2 -> 5 -> 1일까요? 아닙니다. 왜냐하면 2 -> 55 -> 1로 가는 최소 비용에 대한 경로를 구해주어야하기 때문입니다. 이렇기에 재귀를 통해 k에 대해서 i->k, k->j에 대한 최소 비용 경로를 구해주며 더해나가면 i->j에 대한 최소비용 경로를 구해낼 수 있는 것입니다. 이래도 잘 이해가 가시지 않는다면 아래 코드를 참조해보시는 것도 좋을 것 같습니다^^


코드

# 11780번 플로이드 2
import sys
INF = sys.maxsize


# 최소 비용 경로를 구하는 재귀함수
def find_path(i, j):
    if trace[i][j] == 0:
        return []

    k = trace[i][j]
    return find_path(i, k) + [k] + find_path(k, j)


n = int(sys.stdin.readline())

dp = [[INF] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dp[i][i] = 0

for _ in range(int(sys.stdin.readline())):
    x, y, c = map(int, sys.stdin.readline().split())
    dp[x][y] = min(dp[x][y], c)

trace = [[0] * (n+1) for _ in range(n+1)]
for k in range(1, n+1):                # 플로이드-와샬
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
                trace[i][j] = k                                    # 최소 비용이 업데이트 될때 k도 함께 저장

for i in range(1, n+1):
    for j in range(1, n+1):
        print(dp[i][j] if dp[i][j] != INF else 0, end=' ')
    print()

for i in range(1, n+1):
    for j in range(1, n+1):
        if dp[i][j] in [0, INF]:
            print(0)
            continue
        path = [i] + find_path(i, j) + [j]
        print(len(path), end=' ')
        print(*path)
반응형

BELATED ARTICLES

more