[최단 경로] [Python] 10217. KCM Travel - GOLD Ⅰ

본 게시글은 PC버전에 최적화 되어있습니다.

 

10217번: KCM Travel

 

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다. 이어서 K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착공항 v (1 ≤ u, v ≤ N, u ≠ v), 비용 c (1 ≤ c ≤ M, 정수), 그리고 소요시간 d (1 ≤ d ≤ 1,000) 가 공백으로 구분되어 주어진다. 인천은 언제나 1번 도시이고, LA는 언제나 N번 도시이다

출력

각 테스트 케이스당 한 줄에 찬민이 LA에 도착하는 데 걸리는 가장 짧은 소요시간을 출력한다.

만약, LA에 도착할 수 없는 경우 "Poor KCM"을 출력한다.

---

해결 방법

이 문제를 처음 접했을 때는 소요 시간을 우선으로 탐색하되 비용까지 고려해야하는 문제라고 생각했다.

소요 시간이 짧은 순으로 최단 경로를 탐색하면서 최단 경로의 비용이 총 지원 비용을 초과해버리는 경우에

Poor KCM을 출력하면 되는 간단한(?) 문제라고 생각했다.

 

그렇게 구현을 하고 실행을 돌렸는데?

 

허허...

 

이 문제는 구글링을 통해 해결한 문제이다...ㅠ

 

이 문제에서 중요한 점은 소요 시간은 짧지만 비용이 비싼 경우, 소요 시간은 길지만 비용이 싼 경우 위의 두 경우를 모두 탐색해야한다는 것이다. 단순히 소요 시간으로 다익스트라를 돌리게 되면 당연히 소요 시간이 짧은 경로로 다익스트라가 진행되고 우리가 원하는 결과를 얻을 수 없게 될 수도 있다. (그래서 틀리기도 했고...) 아무튼 구글링을 통해 얻은 것은 DP를 통해 해결하고 있었다.

 

우선 내가 처음으로 구현한 코드이다.

 

일반적인 다익스트라에 한 가지 가중치(비용)을 추가하여 최단 소요 시간 경로로 진행했을 경우의 비용을 저장하도록 구현했다.

주어진 입력 값에서는 문제가 없었다. 하지만 역시 반례. 

 

다음과 같은 상황을 고려해보자.

위에서 언급했던 것처럼 내가 구현한 다익스트라는 소요시간을 기준으로 최단거리를 탐색하므로

1. 소요 시간은 짧지만 비용이 비싼 경우

2. 소요 시간은 길지만 비용이 싼 경우

당연히 1번 경로로 진행하게 된다. 하지만 1번 경로의 비용이 총 지원비용을 초과하게 되면 Poor KCM이 출력될 것이다.

2번 경로가 비록 1번 경로보다는 소요 시간은 짧지만 비용이 총 지원비용 이내로 들어올 수 있기 때문에 2번 경로로는 진행이 가능할수도 있는데 말이다. 결과적으로 로직 자체가 문제가 있었고 갈아엎어야했다.

 

구글링을 통해 얻은 코드는 DP를 통해 해결하고 있었다.

"주어진 정점 X 총 지원비용" 크기의 배열을 생성하고 INF로 초기화 해줬다.

한마디로 모든 정점에 대해 총 지원비용 이내에 해당하는 모든 금액으로 탐색을 진행한다는 의미였다.

출발 지점은 1번 공항, 1번 공항에 대한 비용은 0원, 소요시간도 0이므로 clock[1][0] = 0이 된다.

 

이후 다익스트라와 같게 조건을 탐색해서 DP 값을 변경해주면 된다.

최종적으로 도착 공항(=N)의 최소값을 리턴해주면 되는데 그 이유는 간단하다.

DP는 현재 2차원배열로 선언되어 있는데 MIN(DP[N])을 하게 되면 도착 공항에 갈 수 있는 최소 소요 시간을 찾을 수 있기 때문이다. 만약 이 값이 INF인 경우 도착 공항에 도달할 수 없는 경우이므로 "Poor KCM"을 출력하면 된다.

 

실패쓰... Python으로는 통과가 안된다.

이래서 골드1 문제였나보다. 생각을 두 번 하게 만드는 문제다. 분발하자.

 

파이썬으로 구현한 코드이다.