백준 [BOJ] 10217 : KCM travel

10217번: KCM Travel

조건이 있는 최단거리를 찾는 문제.

 

한 도시에서 다른 도시로 가는 최단 거리를 찾는 것이므로

 

이런 경우에는 다익스트라 알고리즘을 쓰는게 좋다고 알려져있다.

 

 

 

단순 dfs / bfs 를 사용하는 경우는 가중치가 모두 같은 경우이다.

 

방문했던 곳에서는 다시 탐색을 진행하지 않는 특성 탓이다.

 

시작점 ~ 방문해야 할 지점까지의 거리를 s라고 하자.

 

만약 가중치가 다른 상황에서 이미 방문했던 곳을 재방문했다고 해보자

 

재방문 했을 때 기존의 값을 수정해야 할 필요가 있으면,

 

그 지점을 기준으로 그 뒤에 있는 모든 경로에 대한 정보를 수정해야한다.

 

이는 거리 s가 더 먼 지점을 먼저 탐색하고, 나중에 s가 더 짧은 지점을 방문하는 경우가 생기기 때문이다.

 

시작점과의 거리에 상관없이 마구잡이로 탐색하는 것은

 

굉장히 비효율적이다.

 

 

 

단순 그래프 탐색(bfs/dfs)가 가중치가 모두 동일한 곳에서 가능한 이유는,

 

가중치가 모두 동일하기 때문에 탐색 수행한 횟수가 곧 최단거리이며,

 

그렇기 때문에 항상 최단거리 순으로 방문하는 것이 보장되기 때문이다.

 

 

 

이를 보완하는 것이 다익스트라 알고리즘이다.

 

즉, 항상 s가 작은 곳부터 순차적으로 방문하게 되면, 

 

해당 정점은 다시는 방문할 필요가 없고, 최소한의 수정만 일어나게 된다.

 

설명 편의 상 가방이 하나 있다고 하자. 

 

1. 현재 정점에서 갈 수 있는 모든 정점에 대한 비용을 확인 및 수정하고, 정점들을 다 가방에 때려넣는다.

 

2. 가방에서 최소비용이 드는 정점 하나를 꺼내 방문한다.

 

목적지에 도달할 때까지 위의 과정을 반복한다.

 

 

위에서 말한 가방은 힙의 역할을 하고 있다.

 

힙은 삽입 연산과 삭제 연산에 모두 O(logN)의 시간복잡도를 갖는다.

 

모든 정점을 한 번씩 방문해야하고,

 

연산은 [ 1) 방문해야 할 최소 값을 힙에서 삭제하는 연산, 2) 방문한 정점의 값을 삽입하는 연산. ]

 

1) 모든 정점(V)에서 다음 정점으로 가는 최소값을 뽑아내는 연산(logV)이 한번씩 있다. O(V * logV)

 

2) 해당 정점에서 인접한 모든 정점(E)을 힙에 삽입(logV)해야한다. O(E * logV)

 

따라서 시간복잡도는 O((V+E)logV) 이다.

 

---

 

알고리즘 설계

 

그런데 이 문제에서는 조건이 하나 있다.

 

정해진 비용 안에서의 최단 거리라는 것이다!

 

탐색을 진행하면서, 정해진 비용을 초과하지 않는 선에서 최소값을 찾는 것이다.

 

이는 냅색 문제와 비슷한데,

 

[냅색] 가방의 한계 무게를 넘지 않으면서, 가치의 최대값이 되도록 한다.

 

[현재] 여행의 한계 비용을 넘지 않으면서, 거리의 최소값이 되도록 한다.

 

갈 수 있는 정점들을 가방에 골라담으면서 최소값이 되도록 하면 되는 것이다.

 

따라서 [ row : 정점 / col : 비용 / 해당 칸의 값 : min(시간) ] 인 배열이 필요한 것이다.

 

dp[v][c] : 해당 정점까지 비용c로 갈 수 있는 최소시간

 

위의 배열에 기록하면서 탐색을 진행하면된다.

 

만약 총 비용이 10이고, v1 -> v3 : 비용4, 시간 7 이라고 해보자.

 

배열의 정의에 따라 dp[3][4] = 7 이 된다.

 

이때 dp[3][10]의 값을 구해야한다.

 

더 많은 비용으로 해당 정점을 방문할 수 있으므로, dp[3][4] = dp[3][5] = dp[3][6] = ... = dp[3][10]이 성립한다.

 

3번 정점까지 비용10으로 갈 수 있는 최소시간이라는 정의 상으로도 맞다.

 

물론 다른 경로가 많다면 중간에 더 작은 값이 있다면 그 값은 바꿀 수 없다.

 

v1->v2->v3 경로의 비용이 7, 시간이 6이라고 해보자.

 

dp[3][7] = 6 이다.

 

dp[3][4] = dp[3][5] = dp[3][6] < dp[3][7] = ... = dp[3][10] 이 성립한다.

 

따라서 배열에 기록할 때, 기록한 곳을 기준으로 하여

우측으로 이동하면서 더 작은 값이 나오기 전까지는 자신의 값을 채워넣어야 한다.

 

- 필요한 변수 - 

1. 가방 역할을 하는 최소힙 priority_queue<>

2. 간선 객체 edge 

3. 간선을 모아두는 리스트 edgeList

4. 방문 기록을 저장하는 dp[v][c] - 정점 v를 한계비용 c로 방문할 때의 최소 시간

 

- 다익스트라 함수 -

[INPUT]

• 정점 개수 N

• 최대 한계 비용 M

[OUTPUT]

• NONE

[RETURN]

• TRUE : 최종 목적지에 한계비용으로 도달할 수 있으면 

• FALSE : 최종 목적지에 한계비용으로 도달할 수 없으면

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 1000000000

struct edge {int e, c, d;};
struct cmp {
	bool operator()(edge a, edge b) {
		return a.d > b.d;
	}
};
int dp[101][10001];
vector<vector<edge>> edgeList;
bool doit(int M, int N);

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	int T, N, M, K, u, v, c, d;

	cin >> T;
	while (T--) {
		cin >> N >> M >> K;

		for (auto& i : dp)
			for (auto& j : i)
				j = INF;
		edgeList.clear(); edgeList.resize(N + 1);


		for (int i = 0; i < K; i++) {
			cin >> u >> v >> c >> d;
			edgeList[u].push_back({ v, c, d });
		}

		if(doit(M,N))	
			cout << dp[N][M] << "\n";
		else
			cout << "Poor KCM\n";

	}

	return 0;
}

bool doit(int M, int N) {
	priority_queue<edge,vector<edge>,cmp> q; // 최소힙

	q.push({ 1,0, 0 }); // 정점, 비용, 시간
	dp[1][0] = 0;

	while (!q.empty()) {
		int cur = q.top().e;
		int cost =  q.top().c;
		int duration = q.top().d;
		q.pop();

		if (cur == N) 
			return true;
		
		if (dp[cur][cost] < duration)
			continue;
            
		for (const auto& edge : edgeList[cur]) {
			int next = edge.e;
			int next_cost = edge.c + cost;
			int next_duration = edge.d + dp[cur][cost];			

			if (next_cost > M) continue;

			if (next_duration < dp[next][next_cost] ) {
				for (int i = next_cost; i <= M; i++) {
					if (dp[next][i] > next_duration)
						dp[next][i] = next_duration;
					else break;
				}
				q.push({ next, next_cost, next_duration });
			}
		}
	}
	return false;
}