백준 10217번 : KCM Travel in Python

10217번: KCM Travel

 

www.acmicpc.net

이 문제는 기존의 최단 경로 문제에 비용 제한이라는 추가 조건이 주어진 경우로 단순히 Dijkstra 알고리즘만으로는 풀기 어려운 문제이다. 그래서 제한된 용량에 물품들을 넣어 물품의 가치의 총합을 가장 높이는 방법을 찾는 냅색 문제에 착안해 이의 풀이 방법인 Dynamic programming을 이용한다.

우선 (제한된 비용+1)과 (공항의 수+1)를 각각 행과 열로 하는 행렬을 만들고 (0, 1)을 제외한 모든 entry의 값을 sys.maxsize(INF)로 한다. 그리고 모든 행과 열에 대해 순회하면서 접근 가능한 정점을 찾아 그와 인접한 정점들에 대해 relax를 한다. 이때 relax하기 전에 비용이 제한 비용을 초과하지 않게 주의해야 한다.

처음에는 이렇게 하지 않고 Dijkstra 알고리즘과 DP를 적절히 이용해 계산하려 했지만 이 경우 비용이 싸지만 거리가 먼 경우와 비용이 비싸지만 거리가 가까운 경우 모두를 고려하지 못해 자꾸 오답이 나왔다. 그래서 구글링해서 알아본 결과 dynamic programming만을 이용해 풀면 비록 오래 걸리긴 하지만 풀이 방법이 비교적 간단해 이 방법을 채택했다.

이를 코드로 구현하면 다음과 같다.

import sys
T = int(input())
for _ in range(T):
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(K):
        u, v, c, d = map(int, input().split())
        graph[u].append([v, c, d])
    # dynamic programming을 구현할 행렬
    dp = [[sys.maxsize]*(N+1) for _ in range(M+1)]
    # 초기값 설정
    dp[0][1] = 0
    for m in range(M+1):
        for u in range(N+1):
            if dp[m][u] == sys.maxsize: continue
            t = dp[m][u]
            for v, c, d in graph[u]:
                # 비용 제한을 넘어서는 경우를 주의한다.
                if m+c > M: continue
                # relax
                elif dp[m+c][v] > t+d:
                    dp[m+c][v] = t+d
    res = sys.maxsize
    for i in range(M+1):
        if res > dp[i][N]:
            res = dp[i][N]
    if res == sys.maxsize:
        print("Poor KCM")
    else:
        print(res)