취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25500번 문제인 무자비한 최단 경로이다.
문제는 아래 링크를 확인하자.

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

문제에 주어진 그래프를 그대로 모델링해 최단경로 알고리즘(dijkstra 등)을 이용해 문제를 해결하고 싶으나, 그러기에는 간선이 너무 많아 시간이 너무 오래걸린다. 묘사할 필요가 없는 에지(해당 에지를 제외하더라도 최단거리가 변하지 않는 에지)를 제외해 에지의 수를 O(N)개로 줄여 그래프를 모델링해 문제를 해결해보자.

x와 y좌표의 경우, 모든 두 마을 사이의 x좌표의 차이와 y좌표의 차이 거리의 두 개의 에지가 모두 있는 그래프를 기본적으로 생각할 수 있다. (모두 그려두면 그중 값이 작은 에지를 최단거리를 탐색할 때 자연스레 이용할 것이기 때문이다.) 이 때, 어떤 세 마을의 x좌표 x1, x2, x3에 대하여 x1<x2<x3이 성립하면 x1과 x3을 잇는 x방향의 차의 에지는 지워져도 대신 x1에서 x2까지 x좌표 차만큼의 가중치의 에지와 x2에서 x3까지 x좌표 차만큼의 가중치의 에지를 이용해 여전히 같은 가중치로 이동할 수 있음을 관찰하자.

위의 관찰을 일반화하면 x좌표 사이의 거리에 관한 모든 에지는 x좌표 오름차순으로 인접한 두 마을 사이의 에지만으로, y좌표 사이의 거리에 관한 모든 에지는 y좌표 오름차순으로 인접한 두 마을 사이의 에지만으로 전부 표현할 수 있음을 알 수 있다.

z좌표의 경우, z를 K로 나눈 나머지가 p인 지점과 K-p(단, p가 0일 경우 0)인 지점 사이의 간선을 긋는 것을 먼저 생각해볼 수 있다. 그러나 해당 쌍을 직접 모두 잇는다면 에지가 O(N^2)개 생길 수 있으므로 이 또한 최적화를 해주어야 한다.

z를 K로 나눈 나머지가 p인 지점이 모이는 가상의 노드를 만들어 각 나머지가 p인 지점에서 해당 노드로의 가중치 z의 방향에지를 이어주고, 이 노드에서 나머지가 K-p(단, p가 0일 경우 0)인 각 노드로의 방향에지를 이어주면 에지를 O(N)개로 z방향의 모든 이동을 표현할 수 있게 된다.

위와 같이 그래프를 모델링하면 주어진 문제의 상황을 O(N)개의 에지로 이루어진 그래프로 모델링할 수 있게 된다. 이 그래프 위에서 dijkstra 등의 최단경로 알고리즘을 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef unsigned int uint;

int N, K;
pair<uint, int> vecX[200000];
pair<uint, int> vecY[200000];
vector<pair<int,uint>> G[400000];
uint dist[400000];

void dijkstra() {
	priority_queue<pair<uint, int>, vector<pair<uint,int>>, greater<>> pq;
	dist[0] = 1;
	pq.push(make_pair(1, 0));

	while (!pq.empty()) {
		int cur = pq.top().second; uint d = pq.top().first; pq.pop();
		if (dist[cur] < d) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first; uint dd = p.second;
			if (dist[nxt] == 0 || dist[cur] + dd < dist[nxt]) {
				dist[nxt] = dist[cur] + dd;
				pq.push(make_pair(dist[nxt], nxt));
			}
		}
	}
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		uint x, y, z; cin >> x >> y >> z;
		vecX[i] = { x,i };
		vecY[i] = { y,i };
		G[i].emplace_back(make_pair(z % K + 200000, z));
		G[(K - z % K) % K + 200000].emplace_back(make_pair(i, z));
	}

	sort(vecX, vecX + N), sort(vecY, vecY + N);
	for (int i = 1; i < N; i++) {
		int n1 = vecX[i - 1].second, n2 = vecX[i].second; uint d = vecX[i].first - vecX[i - 1].first;
		G[n1].emplace_back(make_pair(n2, d));
		G[n2].emplace_back(make_pair(n1, d));
	}
	for (int i = 1; i < N; i++) {
		int n1 = vecY[i - 1].second, n2 = vecY[i].second; uint d = vecY[i].first - vecY[i - 1].first;
		G[n1].emplace_back(make_pair(n2, d));
		G[n2].emplace_back(make_pair(n1, d));
	}
	
	dijkstra();

	for (int i = 0; i < N; i++) cout << dist[i] - 1 << '\n';
}