1. 풀이
간단한 풀이로는 \(O(N^2)\)개의 간선을 모두 생성한 그래프에서 다익스트라를 실행하는 것이다. \(O(N^2logN)\)에 실행될 것이며, 시간 복잡도를 줄일 방법을 고민해야 된다.
첫번째로 문제에서 주어진 \(x, y\)에 대한 거리 공식에 대해 잘 관찰해보자. 백준 2887 행성 터널을 해결했다면, 쉽게 관찰할 수 있는 사실은 각 좌표마다 제일 가까운 것만 간선을 생성해도 괜찮다는 것이다.
구체적으로 설명하자면 어떤 점 \((x, y)\)와 이어야 되는 것은 \(x\)와 가까운 점 2개, \(y\)와 가까운 점 2개를 연결한다는 것이며, 손으로 여러번 그리다 보면 이 간선만으로도 충분히 괜찮다는 믿음이 강하게 생긴다.
두번째로 \(z\)에 한 조건을 잘 살펴보자. \(z\)가 상당히 큰 범위이지만, \(z \mod k\) 범위만 생각해도 된다. 현재 점 \(u (x_u, y_u, z_u)\)에 있고, 점 \(v (x_v, y_v, z_v)\)에 \(z\) 조건을 사용하여 간선을 생성할 조건은 \(z_v = (k-z_u \mod k) \mod k\) 이다.
그렇다면 \(z \mod k\)에 대해 정점을 정렬한다면 연속된 구간의 정점으로 이동한다고 간주할 수 있다. 하지만 전이할 정점이 상당히 많을 수 있으므로, 이에 대해 하나씩 대응하여 간선을 생성하면 최악의 경우에는 \(O(N^2)\)개가 생성될 수 있다.
하지만 백준 5214 환승 문제를 해결해보았다면 더미 노드를 통해 간선을 줄일 수 있다는 아이디어를 쉽게 떠올릴 수 있다. 즉 어떤 \(z \mod k\)에 대한 더미 노드를 생성하고, 이 더미 노드는 \(z \mod k\)와 같은 값을 가지는 실제 정점에 간선을 생성하고, 실제 정점에서는 \(z \mod k\)에 대한 더미 노드로 간선을 생성해주면 된다.
간선을 \(O(N)\)개만 생성했으므로 다익스트라를 사용하여 \(O(NlogN)\)에 문제를 해결할 수 있다.
2. 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k;
struct tup {
ll x, y, z, i;
};
ll f(tup a, tup b) { return min(abs(a.x - b.x), abs(a.y - b.y)); }
struct Q {
ll pos, cot;
};
bool operator<(Q a, Q b) {
return a.cot > b.cot;
}
typedef pair<ll, ll> pi;
#define to first
#define cost second
vector<pi> V[444444];
ll dst[444444];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
vector<tup> arr;
for (int i = 0; i < n; i++) {
ll x, y, z; cin >> x >> y >> z;
arr.push_back({x,y,z,i});
}
sort(arr.begin(), arr.end(), [](auto& a, auto& b) {return a.x < b.x; });
for (int i = 0; i < n; i++) {
if (i)
V[arr[i].i].push_back({arr[i-1].i, f(arr[i], arr[i-1])});
if (i+1<n)
V[arr[i].i].push_back({ arr[i + 1].i, f(arr[i], arr[i + 1]) });
}
sort(arr.begin(), arr.end(), [](auto& a, auto& b) {return a.y < b.y; });
for (int i = 0; i < n; i++) {
if (i)
V[arr[i].i].push_back({ arr[i - 1].i, f(arr[i], arr[i - 1]) });
if (i + 1 < n)
V[arr[i].i].push_back({ arr[i + 1].i, f(arr[i], arr[i + 1]) });
}
for (int i = 0; i < n; i++) {
V[n + arr[i].z % k].push_back({ arr[i].i, arr[i].z});
V[arr[i].i].push_back({n+(k - arr[i].z%k)%k, arr[i].z});
}
priority_queue<Q> pq;
fill(dst, dst + 444444, 1e18);
pq.push({ 0, 0 }); dst[0] = 0;
while (pq.size()) {
Q top = pq.top(); pq.pop();
if (top.cot > dst[top.pos]) continue;
for (auto& l : V[top.pos]) {
if (dst[l.to] > top.cot + l.cost) {
dst[l.to] = top.cot + l.cost;
pq.push({l.to, dst[l.to]});
}
}
}
for (int i = 0; i < n; i++) cout << dst[i] << "\n";
return 0;
}
|
cs |
'PS > 백준' 카테고리의 다른 글
[백준 5979] 납땜하기 (2) | 2022.09.22 |
---|---|
[백준 25491] Mexor tree (0) | 2022.09.14 |
[백준 15506] 정원사 (0) | 2021.12.21 |
[백준 20052] 괄호 문자열 ? (0) | 2021.12.21 |
[백준 17704] Matryoshka (0) | 2021.12.21 |