(C++) 백준 10217 : KCM Travel

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

10217번: KCM Travel

 

 이 문제를 처음봤을 때 바로 배낭문제가 생각 났습니다. 배낭문제는 N개의 물건의 가치와 무게가 주어졌을 때 최대 무게 K를 넘지 않는 선에서 물건 가치 합의 최댓값을 구하는 문제입니다. 배낭문제는 가치와 무게 두가지 요소를 가지고 있으므로 2차원배열을 사용하여 총 무게의 합을 열의 인덱스에, 가치의 합을 각 배열의 값에 대응시켜 물건의 갯수를 하나씩 늘려가며 찾는 방식으로 풀 수 있습니다.  이 문제에서는 소요시간 d와 가격 c가 주어지므로 각각배낭문제의 가치와 무게로 대응할 수 있습니다. 물론 소요시간은 가치와 반대로 짧을수록 좋습니다. 결국 배낭문제에서의 2차원배열 아이디어와 그래프에서 최단거리를 구하는 알고리즘인 다익스트라 알고리즘을 통해 문제를 해결했습니다.

 

문제 풀이

출발공항 u, 도착공항 v , 비용 c, 소요시간 d의 정보를 graph에

각각의 노드까지의 최단거리 - 비용 정보를 담을 2차원 배열 visit을 생성 후 INF로 초기화 해줍니다. 

이후 다익스트라 알고리즘을 적용 해야하는데 이 문제에서의 다익스트라 알고리즘은 다음과 같습니다.

void dijk(int m, int n, std::vector<std::vector<std::tuple<int, int, int>>>& graph, std::vector<std::vector<int>>& visit)
{
	int current_node, current_dis, current_cost, next_node, next_dis, next_cost, cost, dis;
	std::priority_queue<std::tuple<int, int, int>, std::vector<std::tuple<int, int, int>>, cmp> pq;
	pq.emplace(1, 0, 0);
	for (int i = 0; i <= m; i++)
		visit[i][1] = 0;
	while (!pq.empty())
	{
		std::tie(current_node, current_cost, current_dis) = pq.top();
		pq.pop();
		if (current_node == n) break;
		if (visit[current_cost][current_node] < current_dis) continue;
		for (auto next : graph[current_node])
		{
			std::tie(next_node, cost, dis) = next;
			next_dis = dis + current_dis;
			next_cost = cost + current_cost;
			if (next_cost > m || next_dis >= visit[next_cost][next_node]) continue;
           	 	visit[next_cost][next_node] = next_dis;
			pq.emplace(next_node, next_cost, next_dis);
		}
	}

}

1.   출발지점인 노드(=공항) 1에 0을 넣고 큐(각각 노드, 노드까지의 비용, 노드까지의 소요시간)에 현재 노드의 정보를 push합니다.  (출발지로 되돌아 오는 경우는 없으므로 노드 1에서 모든 비용을 0으로 만들어도 됩니다)

 

2.    큐에서 현재 노드의 정보를 가져와서 현재 노드에 연결되어 있는 모든 edge( =현재 공항에서 다음 공항까지의 경로 ) 를 확인합니다.

 

3.    각각의 edge를 통해 다음 노드로 갈 때 비용이 M보다 커지거나 이전에 방문 했을 때의 소요시간이 더 짧은 경우에는 continue하고 아닌 경우일때만 visit을 갱신하고 큐에 추가해줍니다.

 

4.    N번째 노드에 도착하지 않았거나 큐가 남아있다면 2번으로 돌아가고 아니면 종료합니다.

 

이러한 과정을 통해 1번 노드(=인천)에서 부터 N번 노드(=LA)까지 비용이 M보다 작거나 같을 때의 최단거리를 구할 수 있습니다. 기존의 다익스트라 알고리즘에서 사용하는 visit을 응용하여 노드까지 비용이 C일 때의 소요시간이 D, 즉 visit[비용][노드]=소요시간 와 같이 만들 수 있습니다. 이렇게 해야하는 이유는 총 비용이 M을 넘으면 안되기 때문에 각 노드까지의 단순 최단시간을 구해도 비용이 무지막지하게 커질 수도 있기 때문입니다. (시간이 오래걸린다고 무조건 비싸지 않기 때문입니다. 예를들어 시간은 1만큼 걸리는데 비용이 1000일 수도있습니다. 즉 시간과 비용은 독립적이라는 의미 입니다) 따라서 각 노드에서 특정 비용일 때의 최단시간을 구함으로써 노드 N에서의 각 비용에 대한 최단시간을 구할 수 있게 됩니다. 

 

 

 

 

 

 

 

위에서의 다익스트라 코드로도 이 문제는 풀리지만 이보다 더 실행시간을  줄일 수 있는 방법이 있습니다. 

바로 visit을 갱신할 때의 cost 이상의 모든 visit을 갱신해 주는 것입니다.

for (auto next : graph[current_node])
{
	std::tie(next_node, cost, dis) = next;
	next_dis = dis + current_dis;
	next_cost = cost + current_cost;
    
	if (next_cost > m || next_dis >= visit[next_cost][next_node]) continue;
    
	for (int i = next_cost; i <= m; i++)
	{
		if (visit[i][next_node] > next_dis)
			visit[i][next_node] = next_dis;
		else
			break;
	}
	pq.emplace(next_node, next_cost, next_dis);
}

 next_cost보다 더 큰 부분에 대해 next_dis가 더 작으면 전부 교체해 줍니다. 왜 이렇게 할 수 있냐면 비용이 더 큰데 소요시간도 더 오래걸리는 경우는 무조건 제외할 수 있기 때문입니다. 따라서 비용이 더 큰부분을 모두 갱신하여 비용과 거리가 모두 더 큰경우 재방문하는 경우를 없애 시간을 단축 시킬 수 있게됩니다. 

 

전체 소스코드입니다.

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include<tuple>


#define min(a,b) (a<b ? a:b)

#define INF INT_MAX

struct cmp
{
	bool operator()(std::tuple<int, int, int> a, std::tuple<int, int, int> b)
	{
		return std::get<2>(a) > std::get<2>(b);
	}
};

void dijk(int m, int n, std::vector<std::vector<std::tuple<int, int, int>>>& graph, std::vector<std::vector<int>>& visit)
{
	int current_node, current_dis, current_cost, next_node, next_dis, next_cost, cost, dis;
	std::priority_queue<std::tuple<int, int, int>, std::vector<std::tuple<int, int, int>>, cmp> pq;
	pq.emplace(1, 0, 0);
	for (int i = 0; i <= m; i++)
		visit[i][1] = 0;
	while (!pq.empty())
	{
		std::tie(current_node, current_cost, current_dis) = pq.top();
		pq.pop();
		if (current_node == n) break;
		if (visit[current_cost][current_node] < current_dis) continue;
		for (auto next : graph[current_node])
		{
			std::tie(next_node, cost, dis) = next;
			next_dis = dis + current_dis;
			next_cost = cost + current_cost;
			if (next_cost > m || next_dis >= visit[next_cost][next_node]) continue;
			for (int i = next_cost; i <= m; i++)
			{
				if (visit[i][next_node] > next_dis)
					visit[i][next_node] = next_dis;
				else
					break;
			}
			pq.emplace(next_node, next_cost, next_dis);
		}
	}

}


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	int T, N, M, K, u, v, c, d, result;
	std::cin >> T;
	while (T--)
	{
		result = INF;
		std::cin >> N >> M >> K;
		std::vector<std::vector< std::tuple<int, int, int>>> graph(N + 1);
		std::vector<std::vector<int>> visit(M + 1, std::vector<int>(N + 1, INF));
		for (int i = 0; i < K; i++)
		{
			std::cin >> u >> v >> c >> d;
			graph[u].emplace_back(v, c, d);
		}
		dijk(M, N, graph, visit);
		for (int i = 1; i <= M; i++)
		{
			result = min(result, visit[i][N]);
		}
		if (result == INF)
			std::cout << "Poor KCM\n";
		else
			std::cout << result << "\n";
	}

}