BOJ 17242 Kaka & Bebe

* BOJ 17242 Kaka & Bebe

[분류 - 최단 경로/ 그리디]

  최단 경로를 구하는 문제.

  뭐랄까 각 정점당 상태를 나타내고자하면 c의 상한이 1000이고 d의 상한 역시 1000이므로 1000 x 1000의 상태를 가질 수 있다.. 최대 정점의 수가 1000이니, 이를 모두 표현하고자 한다면 1000000000 = 10^9이므로 시간초과가 날 것임을 명확하게 알 수 있습니다.

[해설]

  전제 1) 각 정점에 대한 상태는 1000개 이하면 충분하다.

  전제 1 증명) 각 정점당 1000 x 1000의 상태를 가질 수 있다곤 했는데,, 과연 1000 x 1000 상태가 모두 등장하는 경우가 있는지 생각해봅시다. 최단 경로 그리디 알고리즘 다익스트라를 쓴다면, 또는 상태에 대한 단순 BFS를 쓴다면 이전 정점이 최단 거리가 이미 계산 됐으므로 최대 진입 간선 1000개가 들어올 수 있습니다. 그러면? 상태는 최대 1000개가 되겠죠.

  전제 2) k번째 정점에 대해 상태 (cj, dj)를 방문해야할 때, 이전 상태 (ci, di)에 대해 라면 상태 (cj, dj)를 굳이 방문할 필요가 없다.

  전제 2 증명) 너무 명확하죠. 이라면 이므로 최소를 유지하기 위해 굳이 방문할 필요가 없습니다.

  전제 2)에 의해 정점에 대한 상태는 c 기준으로 정렬을 한다면 임의의 인덱스 i, j에 대해 아래 조건을 만족합니다.

  여기서 이진 검색 트리를 구성하는 것이 꽤 유용해보입니다. [조건 1]을 만족하도록 이진 탐색 트리를 구성해주시면 되겠습니다. 이 부분 문제는 알고스팟의 "너드인가, 너드가 아닌가 ?(https://algospot.com/judge/problem/read/NERD2)" 문제와 동일합니다.

  저는 상태 방문 BFS로 문제를 풀었으며, 새로운 상태가 생길 때마다 위 [조건 1]을 만족하는 이진 탐색 트리를 유지하게끔 했습니다.

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int MAX_N = 1e3, INF = 1e9;
struct _d { int v, c, d; };
int main() {
	vector<_d> adj[MAX_N];
	int N, M, u, v, c, d, ans;
	queue<_d> q;
	map<int, int> dist[MAX_N];
	scanf("%d%d", &N, &M);
	while (M--) {
		scanf("%d%d%d%d", &u, &v, &c, &d);
		adj[u].push_back(_d{ v,c,d });
		adj[v].push_back(_d{ u,c,d });
	}
	dist[0][-1000] = -1000;
	q.push(_d{ 0, 1000, 1000 });
	while (!q.empty()) {
		_d u = q.front(); q.pop();
		for (_d& v : adj[u.v]) {
			c = u.c + v.c, d = u.d + v.d;
			if (c <= 2000 && d <= 2000) {
				c = -c, d = -d;
				auto it = dist[v.v].lower_bound(c);
				if (it == dist[v.v].end() || it->second < d) {
					if (it != dist[v.v].begin()) {
						it--;
						while (it->second < d) {
							if (it == dist[v.v].begin()) {
								dist[v.v].erase(it);
								break;
							}
							else {
								it = dist[v.v].erase(it);
								it--;
							}
						}
					}
					dist[v.v][c] = d;
					q.push(_d{ v.v, -c, -d });
				}
			}
		}
	}
	ans = 1e9;
	for (auto it = dist[N - 1].begin(); it != dist[N - 1].end(); it++)
		ans = min(ans, (it->first + 1000) * (it->second + 1000));
	printf("%d", ans == 1e9 ? -1 : ans);
	return 0;
}

이상하게 일반 순회하는 것이 더 빠른 이유는 무엇..

이 소스는 이진 탐색하지 않고 단순 순회하는 것으로 되어 있습니다.

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int MAX_N = 1e3, INF = 1e9;
struct _d { int v, c, d; };
int main() {
	vector<_d> adj[MAX_N];
	int N, M, u, v, c, d, ans, can;
	queue<_d> q;
	set<pair<int,int>> dist[MAX_N];
	scanf("%d%d", &N, &M);
	while (M--) {
		scanf("%d%d%d%d", &u, &v, &c, &d);
		adj[u].push_back(_d{ v,c,d });
		adj[v].push_back(_d{ u,c,d });
	}
	dist[0].insert({0, 0});
	q.push(_d{ 0,0,0 });
	while (!q.empty()) {
		_d u = q.front(); q.pop();
		for (_d& v : adj[u.v]) {
			c = u.c + v.c, d = u.d + v.d;
			if (c <= 1000 && d <= 1000) {
				can = 1;
				for (auto it = dist[v.v].begin(); it != dist[v.v].end(); ) {
					if (it->first <= c && it->second <= d) {
						can = 0;
						break;
					}
					else if (it->first >= c && it->second >= d)
						it = dist[v.v].erase(it);
					else it++;
				}
				if (can) {
					dist[v.v].insert({ c, d });
					q.push(_d{v.v, c, d});
				}
			}
		}
	}
	ans = 1e9;
	for (auto it = dist[N - 1].begin(); it != dist[N - 1].end(); it++)
		ans = min(ans, it->first * it->second);
	printf("%d", ans == 1e9 ? -1 : ans);
	return 0;
}