[백준 10217 파이썬] KCM Travel (플래티넘 5, DP)

알고리즘 유형 : DP (냅색)
풀이 참고 없이 스스로 풀었나요? : X

https://www.acmicpc.net/problem/10217

SOLVE 1

전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이

import sys
import math
input = sys.stdin.readline
INF = math.inf

for _ in range(int(input())):
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    knapsack = [[INF]*(M+1) for _ in range(N+1)]
    knapsack[1][0] = 0 # 출발 노드의 최단 시간 값 0으로 초기화
    
    for _ in range(K):
        u, v, c, d = map(int, input().split())
        graph[u].append((v, c, d))
    
    # 비용 0부터 시작하여 1씩 올리면서, 비용 K를 사용했을 때(column)
    # 어떤 노드(row)까지 도달하는 최단 시간 값이 존재하고 있다면(not INF),
    # 그 노드의 인접 노드들의 최단 시간 값을 비교&갱신해준다.
    for cost in range(M+1):
        for city in range(1, N+1):
            if knapsack[city][cost] != INF:
                for adjacency_city, c, d in graph[city]:
                    cal_d = knapsack[city][cost] + d
                    cal_c = cost + c
                    
                    # 인접 노드로 이동하고 난 비용이 M 이하여야함.
                    if cal_c <= M and cal_d < knapsack[adjacency_city][cal_c]:
                        knapsack[adjacency_city][cal_c] = cal_d
    
    # 비용 0을 사용하여 N으로 가는 최단 시간, 비용 1을 사용하여, ..., 이들 중
    # 최소인 값을 채택하여 답으로 확정
    result = min(knapsack[N])
    
    if result == INF:
        print("Poor KCM")
    else:
        print(result)

SOLVE 2

전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때의 풀이

import sys
from collections import deque
input = sys.stdin.readline

def solution():
    INF = float('inf')
    for _ in range(int(input())):
        N, M, K = map(int, input().split())
        graph = [[] for _ in range(N+1)]
        knapsack = [[INF]*(M+1) for _ in range(N+1)]

        if M == 0:
            print("Poor KCM")
            continue

        for _ in range(K):
            u, v, c, d = map(int, input().split())
            graph[u].append((v, c, d))

        knapsack[1][0] = 0 # 출발 노드의 최단 시간 값 0으로 초기화
        q = deque([(1, 0, 0)]) # 출발 노드에서부터 BFS 탐색

        while q:
            cnt_city, cnt_cost, cnt_time = q.popleft()

            if cnt_time > knapsack[cnt_city][cnt_cost]:
                continue

            for adc_city, adc_cost, adc_time in graph[cnt_city]:
                cal_cost = cnt_cost + adc_cost
                cal_time = cnt_time + adc_time

                if cal_cost <= M and cal_time < knapsack[adc_city][cal_cost]:
                    # 전체 문제 정의에 의해, 냅색 메모이제이션 리스트에서
                    # 원소가 "예산 column 이하의 비용을 사용하여 가는 최단 거리"이므로
                    # K 비용으로 가능한 최단 경로는 K+1 ~ M 비용에 대해서도 당연히 가능
                    # 하므로 비교 & 갱신해줘야한다.
                    for cost in range(cal_cost, M+1):
                        if cal_time < knapsack[adc_city][cost]:
                            knapsack[adc_city][cost] = cal_time
                        else:
                            break
                    q.append((adc_city, cal_cost, cal_time))
                
        print(knapsack[N][M] if knapsack[N][M] != INF else 'Poor KCM')

if __name__ == '__main__':
    solution()

서론

이 문제는 언뜻 보면 다익스트라 문제로 보인다. 특정 노드에서 특정 노드까지의 최단 시간(가중치)을 구하는게 목적이고, 간선의 가중치가 모두 양수이기 때문이다.

하지만 그리디하게 edge relaxation을 수행하는 다익스트라의 방식을 원활하게 할 수 없는 부분이 존재한다.

조건을 잘 보면, 공항에서 공항으로 이동할 때 "비용" 값이라는 것이 있다.

이 것이 M 이하여야하는 조건이 있기 때문에, 다익스트라로 구한 최단 시간의 비용이 M 초과이면 이 값은 답이 아니게 된다.

즉 특정 노드에 대해 방문하지 않는 인접 노드들 중에, 출발 노드로부터 도착하는 최단 시간 값이 가장 작은 인접 노드를 골라야하는데, 비용 또한 고려해야 할 조건이므로 어떤 노드가 모든 조건을 부합하는 최단 경로인지를 판단할 수 없으므로, 그리디하게 탐색할 수가 없다.

이는 곧 다익스트라 알고리즘으로 풀 수 없다는 뜻이다.

그럼 다른 풀이 방법을 강구해보자.

조건을 보니 비용이 M 이하이다. 냅색 문제에서 자주 보던 패턴이다. 그러니 이 문제를 DP(냅색) 알고리즘으로 풀어보자.

이 문제는 전체 문제를 두 가지 정도로 정의할 수 있는데, 그에 따라 풀이가 상이하다. 상세한 풀이는 아래 내용을 참고하자.

SOLVE 1) 풀이 요약 (전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 때의 최단 시간"으로 둘 때의 풀이)

1. 참고로 이 풀이는 pypy3로 제출해야 통과된다.

   전체 문제를 "출발 노드에서 row 노드까지 정확히 비용 column으로 갈 떄의 최단 시간"으로 정의하면, 냅색 메모이제이션 배열의 행은 노드 번호, 열은 비용이 된다. (참고로 최종 리턴하는 정답의 형태는 전체 문제에서 도출된 값에서 좀 더 가공해야함. 뒤에서 설명)

2. 전체 문제는 곧 냅색 메모이제이션 배열의 원소 값이 무엇을 의미하는지를 내포한다.

   전체 문제를 부분 문제로 나눠보자.

   출발 노드에서 row 노드까지 정확히 비용 K로 갈 때의 최단 시간 = row 노드의 인접 노드 a, b, c, d, ...들에 대하여, 이 중 임의의 인접 노드 P에서 row 노드로 갈 때의 비용과 시간이 c, t일 때, <출발 노드에서 임의의 인접 노드 P까지 비용 K-c로 가는 최단 시간 + t> 값을 mid라고 하자. 이 때 모든 인접 노드들의 mid 값 중 최소 값

3. 이를 바텀업으로 계산하여 답을 구할건데, 이 때 출발 노드로부터 그래프를 쭉 탐색해나가면서 갱신을 해주는 것이 다익스트라의 수행 형태와 유사하다는 것을 알 수 있다.

   물론 그리디하게 탐색할 필요가 없기에 BFS 형태로 탐색해나가면 되고, 해당 노드(이전 노드로부터 비교&갱신된 노드)가 원래 있던 냅색 값보다 크면 conitnue하고, 비교&갱신해주는 부분은 다익스트라와 똑같다.

   그런데 이 방식으로 하면 풀리긴 풀리는데 시간복잡도가 좀 오래 걸린다. 아마 덱의 사용으로 인해 오래 걸리는 것 같다.

   그래서 이 풀이말고 다른 바텀업 방식을 채택했다.

4. 비용 0에서(0열) 최단 시간 값이 존재하는 모든 노드들에 대해 인접 노드들 최단 시간 값을 비교&갱신해주고(출발 노드 비용 + 인접 노드까지의 비용 값 <= M인 경우에만 갱신), 그 다음 비용 1에서 같은 작업을 수행해주고, 그 다음 비용 2, 쭉 가서 비용 M까지 수행해준다.

   이렇게 해서 구한 최적해가 일반해인 이유는, 비용 C, 최단 시간 값 T인(C행 T열) 노드에 대해, 인접 노드로 나아가 edge relaxation을 수행하면, 모든 간선의 시간 값이 양수이기 때문에 반드시 최단 시간 값이 같거나 더 높게 된다.

   즉, 왼쪽 열의 값이 오른쪽 방향의 열에 값에 영향을 주는 구조이므로 왼쪽에서 오른쪽 열로 쭉 업데이트해주는 방식을 수행했을 때 일반해가 보장이 되는 것같다.

   이 후 비용 1~M으로 N번 공항으로 가는 모든 최단 시간 값 중 최소를 출력하면 된다.

SOLVE 2 풀이 요약 (전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때의 풀이)

1. 전체 문제를 "출발 노드에서 row 노드까지 예산 column 내의 비용으로 갈 때의 최단 시간"으로 둘 때 유의할 점은, column의 예산을 가지고 row 노드까지 최단 시간 T로 갈 수 있다면, 그 이상의 예산을 가지고 있을 때는 당연히 아무리 느려도 T 시간 안에는 도착할 수 있다.

   즉, edge relaxation을 수행할 때 냅색 메모이제이션 배열의 C열을 갱신할 때, C+1열, C+2열, ..., M열까지 전부 다 비교&갱신해줘야 됨을 의미한다.

2. 풀이 1번에서 좀 오래 걸려서 채택하지 않았던 방법으로 탐색해나가면서 edge relaxation을 수행하면 된다.

   그 전에, 우선 전체 문제와 부분 문제를 알아보자.

   출발 노드에서 row 노드까지 예산 K 이내로 갈 때의 최단 시간을 time(row, K)라고 하자.

   time(row, K) = min(time(row, K-1), row 노드의 인접 노드 a, b, c, d, ...들에 대하여, 이 중 임의의 인접 노드 P에서 row 노드로 갈 때의 예산과 시간이 c, t일 때, <출발 노드에서 임의의 인접 노드 P까지 예산 K-c 이내로 가는 최단 시간 + t> 값을 mid라고 하자. 이 때 모든 인접 노드들의 mid 값 중 최소 값)

3. 전체 문제를 바텀업으로 구하기 위해, 출발 노드부터 시작하여 인접 노드를 비교&갱신하되, 그 때의 예산 K에 대하여 K+1 ~ M에 대한 최단 시간 값도 같이 비교&갱신해주는 것을 잊지말자.

4. 이 문제를 통해 알게된 사실인데, 일단 이 풀이는 python3으로 제출해도 AC가 뜬다. 그런데 전체 코드를 함수에 집어넣어서 실행하는 식으로 살짝 바꿔주면 시간 복잡도가 절반 가량 줄어든다.

   이유를 알아보니, 함수는 local scope를 가져서 함수 내에서 선언한 변수는 지역변수인데, 이 것은 런타임에 추가될 수 없어서 array에 저장하여 접근이 빠른데, global scope에서 선언된 전역변수의 경우에는 런타임의 딕셔너리에 추가되어 저장 및 읽기 속도가 상대적으로 느리다고 한다.

배운 점, 어려웠던 점

• 추가 조건을 보고 다익스트라만으로 풀기는 어렵겠다는 생각과, 냅색 문제 풀이와 유사한 모습에 처음에는 다익스트라와 냅색의 혼합을 생각했었다.

  그러나 애초에 다익스트라 알고리즘을 그대로 적용할 수 없는 문제였고, 냅색같은 경우는 메모이제이션 배열의 행, 열은 잘 정했는데 원소 값의 정의, 즉 전체 문제와 부분 문제를 잘못 세워서 못 풀었다.

  DP로 최단 경로를 구해본 적이 없어서 어려웠던 것 같다. 이번 경험을 기회로 조금은 대처법을 익힌 것 같다.