boj, 백준) 10217. KCM travel ( C / C++)

1. 문제 링크

www.acmicpc.net/problem/10217

10217번: KCM Travel

2. 문제 개요

M원 이하로 사용하면서 도착지까지 갈 수 있는 최단 경로를 찾는 문제. 1원이든, M원이든 M원 이내에만 들면 되고 그중에서 최단 시간으로 갈 수 있는 경로를 찾자.

 

3. 문제 힌트

DP를 사용해야 한다. 경로를 찾을 때는 다익스트라 알고리즘(logn)으로 구현해서 사용해야 한다.

 

어떻게 DP를 적용할까? 점화식을 찾기에 앞서 왜 DP를 써야 할지 알아보자,

이 문제는 시간(경로) , 비용(돈) 모두 고려해야 한다. 만약 비용을 고려하지 않는다면 어떤 시작점 A에서 어떤 도착점 B로 갈 때 도착할 수 있는 방법 중 비용을 얼마를 사용해서 도착했는지 알 수 있는 방법이 없다. 이 예는 다익스트라(최단경로) 알고리즘만 사용하면 이렇다.

 

이 문제는 비용도 고려해야하기 때문에, 얼마를 써서 어떤 공항에 도착했는지를 나타내는 값이 하나 필요하다.

즉, 어떤 시작점 A에서 어떤 도착점 B로 갈 때, 10원을 써서 도착할 수도 있고 100원을 써서 도착할 수도 있다. 50원을 써서 도착할 수도 있고. 이런 값을 나타내기 위해 DP가 필요하다.

-> 공간복잡도를 늘려서 최적값들을 저장하고 사용하자. (시간복잡도를 줄임, 꼭 DP는 이렇다. 라는건 아니지만,, 이렇게 간단하게 생각해도 될 것 같다.)

 

 

4. 문제 풀이

3번에서 많은 이야기를 해서 풀이 내용에 적을게 많이 없을 것 같다. 다익스트라만 사용하면 위에 적었던 것처럼, 얼마를 써서 최단시간에 왔는지 알 수 없다. 단순히 최단시간만 구한 것이기 때문, M원을 초과해서 최단시간으로 도착한 것 일수도 있다. 그래서 각 정점마다 얼마를 사용하여 도착했는지 구분하는 정보가 필요하다.

 

그래서 DP에 대한 배열로, dp[정점번호][사용한 비용] 으로 나타내었다. 이 배열은 해당 [정점번호]에 [사용한 비용]을 써서 도착했을 때의 최단 시간을 나타낸다. 

여기서 [사용한 비용]은 문제에서 ≤10,000으로 제한하고 있기 때문에 전역으로 선언하여 사용할 수 있다.

 

또, 다익스트라 알고리즘은 O(logn)으로 구현했다.  우선순위 큐를 사용하면 된다. 다익스트라 반복문 내부에서 최솟값을 찾을 때의 시간을 줄인 것이다. 이에 대한 설명은 다른 블로그에 잘 나와있고, 코드는 밑에 첨부하였으니 코드가 보고 싶으시면 밑 5번을 참고하시면 될 것 같습니다.

 

그래서 답을 구할 때는

 

dp[도착점][i]인데 i는 1원에서부터 M원까지 반복하고, 그중에서 최솟값을 찾아 출력하면 된다.

그런데 이 중에 모두 갱신이 되지 않았다면 Poor KCM을 출력하면 된다.

 

코드를 보면 이해가 잘 될 거라 생각합니다.

5. 코드

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct Data {
	int to, cost, time;
};
struct QueueItem{
	int v, cost, time;
};
struct comp {
	bool operator()(const QueueItem &a, const QueueItem &b)const {
		return a.time > b.time;
	}
};

int t;
const int INF = 987654321;
int dist[101][10001] = { 0 };

int main()
{
	scanf("%d", &t);

	while (t--) {

		int ans = INF;
		int n, m, k;
		scanf("%d %d %d", &n, &m, &k);
		vector<vector<Data>> adj;


		for (int i = 1; i <= n; ++i)
			for (int j = 0; j <= m; ++j)
				dist[i][j] = INF;
			
		adj.resize(n + 1);

		for (int i = 0; i < k; ++i) {
			int from;
			Data item;
			scanf("%d %d %d %d", &from, &item.to, &item.cost, &item.time);
			adj[from].push_back(item);
		}

		//거리 오름차순.
		priority_queue<QueueItem, vector<QueueItem>, comp> pq;	//dist, cur.

		dist[1][0] = 0;
		QueueItem start;
		start.v = 1;
		start.cost = 0;
		start.time = 0;
		pq.push(start);

		while (!pq.empty())
		{
			QueueItem cur = pq.top(); pq.pop();

			//갱신할 필요 체크
			if (dist[cur.v][cur.cost] < start.time) continue;

			//갱신할 필요 있음.

			for (Data item : adj[cur.v])
			{
				QueueItem next;
				next.v = item.to;
				next.time = dist[cur.v][cur.cost] + item.time;
				next.cost = cur.cost + item.cost;

				if (next.cost > 10000)	continue;
				if (dist[next.v][next.cost] > next.time)
				{
					dist[next.v][next.cost] = next.time;
					pq.push(next);
				}
			}
		}
		for (int i = 0; i <= m; ++i)
			ans = min(ans, dist[n][i]);
		if (ans != INF)
			printf("%d\n", ans);
		else
			printf("Poor KCM\n");
	}



	return 0;
}

 

 

6. 결과