[BOJ / 10217] KCM Travel 파이썬

문제 링크

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

10217번: KCM Travel

문제

해결 알고리즘

DP, 다익스트라

기존 문제와 다른 점

백준의 최단거리 알고리즘을 차례대로 풀었다면, 이 문제는 다른 시각으로 접근해야 한다.

기존 알고리즘에서 2차 배열을 푸는 문제는 다음과 같이 X, Y축을 다음과 같이 했었다.

	도착점
시 작 점	/
		/
			/
				/
					/
						/

시작점으로 도착점으로 가는 경유로 정사각형의 배열을 사용했을 것이다.

하지만 이 문제는 다르게 접근해야 한다.

위의 표 처럼 가로축과 세로축에 공항과 비용으로 설정하고 다익스트라와 DP를 사용해야 한다.

이 때, 유의해야 할 점은 메모제이션을 기존 DP보다 더 해야 할 것이다.

예를 들어 다음과 같다.

C공항에서 비용 2로 갈 수 있는 최단 거리가 노란색에 적었다고 하자.

그러면 다음과 같을 것이다. 하지만 C공항에서 비용 3과 비용 4로 갈 수 있는 거리가 INF이라면

비용 2로 갈 수 있는 최단거리는 비용 3과 비용 4로도 갈 수 있는 최단거리이다.

그러므로 연한 노란색을 노란색으로 칠해야 한다.

코드[파이썬]

import sys
from collections import deque

input = sys.stdin.readline
INF = sys.maxsize


def main():
	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))
	
	dist = [[INF] * (M + 1) for _ in range(N + 1)]
	dist[1][0] = 0
	
	que = deque([(0, 0, 1)])  # Time Cost Node
	
	while que:
		time, cost, node = que.popleft()
		
		if dist[node][cost] < time:
			continue
		
		for city, c, t, in graph[node]:
			alt_c = cost + c
			alt_t = time + t
			
			if alt_c <= M and alt_t < dist[city][alt_c]:
				for i in range(alt_c, M + 1):
					if alt_t < dist[city][i]:
						dist[city][i] = alt_t
					else:
						break
				que.append((alt_t, alt_c, city))
	
	sol = dist[N][M]
	
	print(sol if sol != INF else 'Poor KCM')


for ___ in range(int(input())):
	main()