LCA(Lowest Common Ancestor) / 최소 공통 조상 알고리즘
LCA(Lowest Common Ancestor) / 최소 공유 조상
목차
1. LCA란?
2. O(N) LCA 알고리즘
3. O(logN) LCA 알고리즘
LCA란?
LCA란 말 그대로 최소 공유 조상이다. 그래프에서 두 노드 각각의 부모들을 쭉 타고 올라갔을 때 최초로 공유하는 부모를 말한다.
이 예시에서 노드 5와 노드 3의 최초 공유 조상은 1이 된다.
이 경우에 노드 12와 노드3의 최소 공유 조상은 1이 된다.
O(N) LCA 알고리즘
자 그러면 이제 LCA 알고리즘을 구현해 봅시다.
LCA 구현을 위해 3가지 단계가 필요합니다.
- 각 노드들의 depth를 구하여 가지고 있는다 ( depth : root 노드부터 자기 노드까지의 거리(깊이))
- LCA를 구하려는 두 노드 중 더 깊은 노드의 depth를 더 낮은 노드의 depth로 맞춘다.
- 이후 두 노드를 같이 한칸씩 parent를 찾아가며 동일한 부모(LCA)가 나올 때 까지 찾는다.
위의 예시로 설명해 보겠습니다.
예시1
1. 각 노드들의 depth를 구하기
=> dfs를 한번 돌려서 전처리 하면 모든 노드의 depth를 구할 수 있습니다.
2. LCA를 구하려는 두 노드 중 더 깊은 노드의 depth를 더 낮은 노드의 depth로 맞춘다.
노드 5의 depth 는 2 / 노드3의 depth는 1입니다. 5번의 depth가 3번 보다 크므로(깊으므로), 5번의 depth가 3번의depth와 같아질 때 까지 5번을 부모를 찾으며 끌어 올려줍니다. 그러면 노드 2번이 됩니다.
=> 노드 5번을 노드2번으로 업데이트 합니다.
3. 이후 두 노드를 같이 한칸씩 parent를 찾아가며 동일한 부모(LCA)가 나올 때 까지 찾는다.
노드 2번, 노드 3번의 부모를 올려가며 탐색하면 최초로 나오는 부모가 1번입니다. 따라서 노드 5번과 노드3번의 LCA는 1이 되겠네요.
예시2
1. 각 노드들의 depth를 구하기
2. LCA를 구하려는 두 노드 중 더 깊은 노드의 depth를 더 낮은 노드의 depth로 맞춘다.
노드 12의 depth가 4, 노드 3의 depth가 1이므로, 노드 4를 depth가 1이 될 때 까지 부모를 찾으며 올려줍니다. ( 2번 노드가 되겠네요)
3. 이후 두 노드를 같이 한칸씩 parent를 찾아가며 동일한 부모(LCA)가 나올 때 까지 찾는다.
2번 노드와 3번 노드의 최초 공유 부모를 찾으면 1번이 됩니다. 즉 LCA는 1번 입니다
이 알고리즘이 왜 O(N)일까요,
부모를 찾아 올라가는 과정에서 최악의 경우 전체 노드의 개수만큼 탐색하여 올라가야 하기 때문입니다.
최악의 경우라하면 노드들이 일자로 연결되어 있는 경우입니다.
백준 문제 :
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
소스코드
|
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
|
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int par[50001];//부모 노드를 저장
int depth[50001];
vector<int> tree[50001];
bool visited[50001];
void dfs(int n) {//DFS를 통해 부모노드, depth를 탐색
visited[n] = true;
for (int i = 0; i < tree[n].size(); i++) {
int now = tree[n][i];
if (!visited[now]) {
par[now] = n;
depth[now] = depth[n] + 1;
dfs(now);
}
}
}
int main() {
cin >> N;
for (int i = 0; i < N-1; i++) {
int x, y;
cin >> x >> y;
tree[y].push_back(x);
tree[x].push_back(y);
}
dfs(1);
cin >> M;
while (M--) {
int a, b;
cin >> a >> b;
if (depth[a] < depth[b]) swap(a, b);//편의상 더 깊이가 깊은 쪽을 a로 설정
while (depth[a] != depth[b]) a = par[a];//depth가 같아질때 까지 부모노드로 업데이트
while (a != b) {//공통 부모 찾기
a = par[a];
b = par[b];
}
cout << a << '\n';
}
}
|
cs |
O(LogN) LCA 알고리즘
위의 방식대로 풀게 되면 노드N * 쿼리 M인 경우 O(N*M)으로 시간초과가 나는 경우가 있습니다.
그래서 더 효율적인 알고리즘을 생각해야 합니다.
방법을 한마디로 정의하자면, 공통부모를 찾아 올라가는 과정을 2^n으로 더 빠르게 뛰어올라가며(?) 찾는 것입니다.
이를 위해서는 자신의 2^n번째 부모를 알고 있어야 합니다.
par[n][i]를 정의한다. par[n][i]는 노드n의 2^i번째 부모입니다.
par[n][0]은 위의 방법에서 부모를 찾았던 방식을 동일하게 이용하면 됩니다.(DFS)
이제 점화식으로 남은 2^i 번째 부모를 채워야합니다.
점화식은 다음과 같습니다.
par[n][i] = par[par[n][i-1]][i-1];
n의 2^i-1번째 부모의(par[n][i-1]) 2^i-1번째 부모가 n의 2^i번째 부모입니다.
이후 방법은 동일합니다.
다만 우리는 2^i번째 부모를 알고 있으므로 더 빠르게 뛰어가듯! 공통 조상을 찾을 수 있습니다.
- 두 노드의 깊이를 맞춰줄 때 ( 한 쪽의 깊이가 더 깊을 때)
앞서 한칸 씩 깊이를 올려가던 과정을 이제는 2^i씩 올려가면서 깊이가 같아지도록 맞춤.
- 두 노드의 깊이를 맞춰 준 후, 공통 조상을 구할 때도 마찬가지로 2^i씩 올려가면서 깊이가 같아지도록 맞춤.
백준 문제 :
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
소스코드
|
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
|
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int par[100001][21];//부모 노드를 저장
int depth[100001];
vector<int> tree[100001];
bool visited[100001];
void dfs(int n) {//DFS를 통해 부모노드, depth를 탐색
visited[n] = true;
for (int i = 0; i < tree[n].size(); i++) {
int now = tree[n][i];
if (!visited[now]) {
par[now][0] = n;
depth[now] = depth[n] + 1;
dfs(now);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for (int i = 0; i < N-1; i++) {
int x, y;
cin >> x >> y;
tree[y].push_back(x);
tree[x].push_back(y);
}
dfs(1);
for(int j = 1; j < 17 ; j++){
for (int i = 1; i <= N; i++) {
int tmp = par[i][j - 1];
par[i][j] = par[tmp][j - 1];
}
}
cin >> M;
while (M--) {
int a, b;
cin >> a >> b;
if (depth[a] < depth[b]) swap(a, b);//편의상 더 깊이가 깊은 쪽을 a로 설정
int gap = depth[a] - depth[b];
for (int i = 20; i >= 0; i--) {
if (gap >= (1 << i)) {
gap -= (1 << i);
a = par[a][i];
}
}
//a와 b의 깊이차이를 2^i씩 올리면서 맞춰줌
if (a == b) {
cout << a << '\n';
continue;
}
else {
for (int i = 20; i >= 0; i--) {
if (par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
}//a, b의 공통 조상을 찾아 나감. 이 때도 2^i씩 올리면서 업데이트
cout << par[a][0] << '\n';
}
}
}
|
cs |