11438번: LCA 2 
문제 링크: 11438번: LCA 2
개요
최소 공통 조상(Lowest common ancestor, LCA)는 트리에 어떤 두 정점 u와 v가 있을 때, u 자신이거나 u의 조상인 동시에 v 자신이거나 v의 조상인 노드들 중 가장 깊은 노드이다. LCA 알고리즘의 기본 흐름은 다음과 같다.
- 두 정점 중 깊이가 더 깊은 정점에서 출발한다.
- 다른 정점의 깊이와 같아질 때까지 부모 노드로 이동한다.
- 깊이가 같은 두 정점에서 동시에 출발하여 부모 노드로 이동한다.
- 한 노드에서 만났을 때 이동을 종료한다.
- 만난 노드가 LCA이며, 총 이동 횟수가 두 노드 간의 최소 거리이다.
전처리 (depth 배열과 parent 배열)
1
2
3
vector<int> tree[MAX_N + 1];
int parent[MAX_N + 1][MAX_LOG_N]; //parent[n][k] : 노드 n의 2^k번째 부모
int depth[MAX_N + 1] = { 0 };
tree[i]는 노드 i와 연결된 모든 노드의 번호를 저장하는 vector이며, depth[i]은 노드 i의 깊이를 저장한다. 노드 1은 루트 노드이기 때문에 depth[1]은 0이다.
i번째 노드의 1번째 부모가 parent[i]인 일차원 배열을 사용해도 위에서 말한 흐름을 따라가며 LCA를 찾을 수 있다. 그러나 해당 방식은 부모 노드로 타고 올라가는 과정의 시간 복잡도가 O(n)이기 때문에 전체 시간 복잡도가 O(n*m)이 되어 이 문제에서는 시간 초과가 발생하게 된다. 따라서 노드 n의 2^k번째 부모(1번째 부모가 바로 위의 노드)를 parent[n][k]에 저장하는 이차원 배열을 사용했다.
parent[n][0]와 depth 배열 채우기
1
2
3
4
5
6
7
8
9
10
11
12
void explore(int currNode) {
for (int i = 0; i < tree[currNode].size(); i++) {
int nextNode = tree[currNode][i];
if (depth[nextNode] == -1) {
parent[nextNode][0] = currNode;
depth[nextNode] = depth[currNode] + 1;
explore(nextNode);
}
}
return;
}
일반적인 DFS의 형태를 가진 재귀 함수이다. 메인 함수에서 explore(1)을 호출하여 루트 노드인 1에서부터 출발해 자식 노드로 내려가며 각 노드의 depth와 parent[n][0] (노드 n의 첫 번째 부모) 에 값을 넣어준다.
parent 배열 나머지 채우기
1
2
3
4
5
6
7
for (int j = 0; j < MAX_LOG_N; j++) {
for (int i = 2; i <= n; i++) {
if (parent[i][j] != -1) {
parent[i][j + 1] = parent[parent[i][j]][j];
}
}
}
explore() 함수가 실행되면서 parent[n][0]만 채워졌다. 노드 n의 2^k번째 부모를 parent[n][k]에 넣어줘야 한다. 어떤 노드 i의 j번째 조상의 j번째 조상은 i의 2*j번째 조상이고, 이는 곧 parent[i][j + 1]이다. 따라서 parent[i][j + 1]는 parent[parent[i][j]][j]의 형태로 나타낼 수 있다.
쿼리 처리하기
depth[u] >= depth[v]로 유지
1
if (depth[u] < depth[v]) { int tmp = u; u = v, v = tmp; };
이후 작업을 편하게 하기 위해 u의 깊이가 v의 깊이보다 깊거나 같게 되도록 조건문을 추가했다.
두 노드의 깊이 맞추기
1
2
3
4
5
int diff = depth[u] - depth[v];
for (int j = 0; diff > 0; j++) {
if (diff % 2 == 1) u = parent[u][j];
diff /= 2;
}
두 노드의 깊이 차이를 diff에 저장해놓고, u의 깊이가 v의 깊이와 같아질 때까지 parent[u]를 이용해 u를 부모 노드로 이동시키는 작업이다. j는 밑이 2인 로그 스케일로 변화하는 변수이기 때문에 2진수 변환과 같은 방법을 이용했다. 부모 노드로 한 칸씩 이동하는 방법보다 훨씬 빠르게 두 노드의 깊이를 맞출 수 있다.
LCS 구하기
1
2
3
4
5
6
7
8
9
10
11
if (u != v) {
for (int j = MAX_LOG_N - 1; j >= 0; j--) {
if (parent[u][j] != -1 && parent[u][j] != parent[v][j]) {
u = parent[u][j];
v = parent[v][j];
}
}
u = parent[u][0];
}
printf("%d\n", u);
두 노드의 깊이가 같아졌으므로 부모 노드가 다른 동안 부모 노드로 한 칸씩 이동해준다. 이동 후 u와 v는 LCS의 바로 자식 노드이기 때문에 마지막으로 한 칸 더 이동 후 출력해준다.
전체 코드
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_N 100000
#define MAX_LOG_N 18
vector<int> tree[MAX_N + 1];
int parent[MAX_N + 1][MAX_LOG_N]; //parent[n][k] : n번째 노드의 2^k번째 부모
int depth[MAX_N + 1] = { 0 };
void explore(int);
int main() {
int n, m;
scanf("%d", &n);
//트리 입력받기
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
//depth, parent 배열 초기화
for (int i = 1; i <= n; i++) {
depth[i] = -1;
for (int j = 0; j < MAX_LOG_N; j++) {
parent[i][j] = -1;
}
}
depth[1] = 0;
//parent[n][0]과 depth 배열 채우기
explore(1);
//parent 배열 채우기
for (int j = 0; j < MAX_LOG_N; j++) {
for (int i = 2; i <= n; i++) {
if (parent[i][j] != -1) {
parent[i][j + 1] = parent[parent[i][j]][j];
}
}
}
//쿼리 입력받기
scanf("%d", &m);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
//depth[u] >= depth[v]로 유지
if (depth[u] < depth[v]) { int tmp = u; u = v, v = tmp; };
int diff = depth[u] - depth[v];
//두 노드의 깊이 맞추기
for (int j = 0; diff > 0; j++) {
if (diff % 2 == 1) u = parent[u][j];
diff /= 2;
}
if (u != v) {
for (int j = MAX_LOG_N - 1; j >= 0; j--) {
if (parent[u][j] != -1 && parent[u][j] != parent[v][j]) {
u = parent[u][j];
v = parent[v][j];
}
}
u = parent[u][0];
}
printf("%d\n", u);
}
return 0;
}
void explore(int currNode) {
for (int i = 0; i < tree[currNode].size(); i++) {
int nextNode = tree[currNode][i];
if (depth[nextNode] == -1) {
parent[nextNode][0] = currNode;
depth[nextNode] = depth[currNode] + 1;
explore(nextNode);
}
}
return;
}