[백준 1376] 민식우선탐색 : 세그먼트 트리의 활용
https://www.acmicpc.net/problem/1376
1376번: 민식우선탐색
첫째 줄에는 정점의 개수 N(<=100,000)과 간선의 개수 M(<=1,000,000)이 주어진다. 두 번째 줄부터 M+1번째 줄 까지는 a b의 형태로 a와 b가 간선으로 연결되어 있다는 의미의 입력이 들어온다. 모든 간선
www.acmicpc.net
단순한 그래프 탐색 문제 같지만 꽤나 까다롭고 악명 높은 문제이기에 풀이를 써 보려 한다.
개요 및 기본 아이디어
탐색 방식은 dfs와 거의 같지만, 방문할 수 있는 정점의 목록을 계속해서 업데이트 해주고, 그 목록의 중간값과 최솟값을 빠르게 구하는 작업이 필요하다. 먼저 주어진 예제를 통해 민식 우선 탐색의 작동 방식을 이해해보자.
먼저 시작점인 1번 정점을 방문한다. 여기서, 이미 방문한 정점은 이후에 고려되지 않아야 하므로, 1번 정점으로 가는 모든 간선을 제거해준다.
다음으로 이동할 수 있는 정점은 2번, 3번, 4번이다. 홀수개가 존재하므로 중간값인 3번 정점을 방문해야 한다. 이번에도 3번 정점으로 가는 모든 간선은 제거해준다.
다음으로는 2번, 4번으로 이동할 수 있다. 짝수개이기 때문에 최솟값인 2번 정점으로 방문한다.
다음으로는 5번을 방문해 준다. 더이상 방문할 정점이 없으므로 다시 3번 정점으로 돌아간다.
이후 마지막 4번 정점을 방문해 준다. 이제 모든 정점을 방문했으므로 민식우선탐색이 종료된다.
입력으로 주어지는 범위가 정점 최대 10만개, 간선 최대 100만개로 꽤나 많기 때문에 중간값이나 최솟값을 찾아서 방문하는 것을 빠르게 수행해야 하며, 이미 방문한 정점은 고려하지 않아야 하므로, 정점을 방문할 때마다 그 정점과 연결된 다른 모든 정점으로부터의 간선을 끊어야 한다. 계속해서 값이 갱신되고, 중간값이나 최솟값을 찾는 작업을 수행하는 것은 세그먼트 트리의 힘으로 가능하지 않을까?
풀이 설계
리프노드에 다른 정점으로의 이동 여부를 담는 구간 합 트리를 정점 갯수만큼 만들어 관리하는 것을 생각해 보자.
예를 들어 8개의 정점이 있고, 1번 정점에서 2, 3, 5 번 정점으로 이동할 수 있다면 1번 정점에 대한 트리는 다음과 같이 설계될 것이다. 여기서 중앙값을 찾기 위해서는 이동할 수 있는 정점 수가 x일 때 x/2+1번째로 작은 정점을 찾으면 되고, 최솟값은 가장 작은 정점을 찾으면 된다. 현재 범위를 절반씩 쪼개면서 왼쪽 범위의 합이 k이상이라면 왼쪽 범위에서 k번째 원소, 반대의 경우 오른쪽 범위에서 k - (왼쪽 범위의 합)번째 원소를 찾는 식으로 O(logN)에 중간값을 구할 수 있다. 그러나 이런 식으로 설계하기 위해서는 O(N^2)의 메모리가 필요하며, 이는 메모리 초과를 피할 수 없다.
이를 최적화하기 위한 방법으로 처음 초기화 할 때부터 모든 정점에 대한 이동 가능 여부를 담지 않고, 이동 가능한 정점들에 대해서만 트리를 만들어 주는 방법이 있다. 이런 식으로 설계하면 N개의 세그먼트 트리에 대해서 만들어도 결국 할당되는 메모리는 간선 수에 비례할 것이기 때문에 O(M)의 메모리를 사용한다. 좌표 압축과 비슷한 원리이다.
또한 이 문제에서 주의해야 할 점이 있다. 이 문제에서는 자기 자신으로 가는 간선과 중복된 간선도 입력으로 들어온다. 어짜피 한 번 방문한 정점을 다시 방문하지 않을 것이므로, 이러한 경우의 간선은 미리 고려 대상에서 제외해야 한다.
|
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <bits/stdc++.h>
using namespace std;
int V, E;
vector<vector<int>> adj, tree;
vector<int> edgeCnt;
vector<int> init(vector<int>& vec) {
vector<int> ret;
int nodeSz = 1;
while (nodeSz < vec.size()) nodeSz <<= 1;
nodeSz <<= 1;
ret.resize(nodeSz);
for (int i = nodeSz / 2; i < nodeSz; i++) ret[i] = 1;
for (int i = nodeSz / 2 - 1; i > 0; i--) ret[i] = ret[i * 2] + ret[i * 2 + 1];
return ret;
}
void update(int i, int ind, vector<int>& vec) {//ind번 간선 없애기
int nodeSz = 1;
while (nodeSz < vec.size()) nodeSz <<= 1;
nodeSz <<= 1;
ind += nodeSz / 2;
if (tree[i][ind]) {
tree[i][ind] = 0;
edgeCnt[i]--;
}
while (1 < ind) {
ind /= 2;
tree[i][ind] = tree[i][ind * 2] + tree[i][ind * 2 + 1];
}
}
int getMid(int i, int k, int l, int r, int now) {
if (l == r) return l;
int mid = (l + r) / 2;
if (tree[i][now * 2] < k) return getMid(i, k - tree[i][now * 2], mid + 1, r, now * 2 + 1);
else return getMid(i, k, l, mid, now * 2);
}
void dfs(int now) {
cout << now << " ";
for (int next : adj[now]) {
update(next, lower_bound(adj[next].begin(), adj[next].end(), now) - adj[next].begin(), adj[next]);
}
int nodeSz = 1;
while (nodeSz < adj[now].size()) nodeSz <<= 1;
nodeSz <<= 1;
while (1) {
if (!edgeCnt[now]) break;
if (edgeCnt[now] % 2) dfs(adj[now][getMid(now, edgeCnt[now] / 2 + 1, 0, nodeSz / 2 - 1, 1)]);
else dfs(adj[now][getMid(now, 1, 0, nodeSz / 2 - 1, 1)]);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> V >> E;
adj.resize(V + 1);
edgeCnt.resize(V + 1); tree.resize(V + 1);
for (int i = 0; i < E; i++) {
int a, b;
cin >> a >> b;
if (a == b) continue;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= V; i++) {
sort(adj[i].begin(), adj[i].end());
adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
edgeCnt[i] = adj[i].size();
tree[i] = init(adj[i]);
}
dfs(1);
}
|
cs |
코드의 내용이다. 시간 복잡도는 O(M + N), 공간 복잡도는 O(M)이다.