LCA - 최소 공통 조상
LCA(Lowest Common Ancestor) 알고리즘이란?
트리에서의 두 정점 u, v에서 가장 가까운 공통 조상을 찾는 알고리즘입니다. 즉, 가장 가까운 공통 조상은 두 정점 u, v를 자손으로 가지는 노드들 중 깊이가 가장 깊은 노드를 의미합니다.
이 글에서는 LCA를 2가지 방법으로 구해보겠습니다. 첫 번째는 O(N)만에 구할 수 있는 알고리즘이고 두 번째 방법은 O(logN)만에 구할 수 있는 알고리즘입니다.
1. O(N) 알고리즘
지금 소개해 드릴 이 방법은 간단합니다. 먼저 알고리즘부터 살펴보겠습니다.
[알고리즘]
1. 두 정점 u, v의 깊이가 같은지 확인합니다. 만약 두 정점의 깊이가 다르다면 두 정점의 깊이가 같아질 수 있도록 한 칸씩 트리를 타고 올라가면서 깊이를 맞춰줍니다.
2. 두 정점 u, v의 깊이가 동일하다면, 이제 두 정점이 공유하는 부모 노드 중 깊이가 가장 깊은 부모 노드를 찾아야 합니다. 이는 두 정점이 같이 한 칸씩 트리를 타고 올라가면서 두 정점이 만나는 지점으로 구할 수 있습니다. (그 지점이 바로 우리가 구하고자 하는 LCA입니다.)
이해를 돕기 위해서 그림으로 위 알고리즘을 적용해 보겠습니다.
아래와 같은 트리가 있을 때 LCA를 구하고자 하는 두 정점을 6번, 8번으로 정했습니다.
먼저 두 노드의 깊이를 살펴보니 깊이가 다릅니다. 깊이가 깊은 8번 노드를 6번 노드의 깊이와 같아지도록 올려보겠습니다.
8번 노드의 깊이를 6번 노드 깊이와 맞춰주었습니다. 이제 5번, 6번에서 시작하여 최소 공통 조상을 찾아가 보도록 하겠습니다. 각 노드가 동시에 트리를 거슬러 올라가다가 만나는 접점이 있을 때 멈추도록 하겠습니다.
아직 두 정점이 만나지 않았으니 한 칸 더 올려보도록 하겠습니다.
위 그림에서 최소 공통 조상이 1번인 것을 확인할 수 있습니다. 이렇게 구현하면 이제 LCA를 O(N)으로 구할 수 있게 된 것입니다!
이 알고리즘을 코드로 구현해 보겠습니다. 아래 코드는 백준 LCA(11437번: LCA (acmicpc.net)) 문제를 기반으로 작성되었습니다.
[코드]
#include<stdio.h>
#include<vector>
#define MAX 50000
#define SWAP(x,y) x^=y^=x^=y
using namespace std;
int parent[MAX+1];
int depth[MAX+1];
vector<int> tree[MAX+1];
int N, M;
void dfs(int cur){
for(int next: tree[cur]){
if(depth[next] == -1){ // 아직 방문하지 않은 점
parent[next] = cur; // next의 부모
depth[next] = depth[cur] + 1; // next의 깊이는 부모 cur보다 +1
dfs(next);
}
}
}
int LCA(int u, int v){
if(depth[u] < depth[v]) SWAP(u,v); // 깊이가 얕은 곳의 정점을 v로 설정
int diff = depth[u] - depth[v];
while(diff>0){
u = parent[u];
diff-=1; // 한 칸씩 올려본다.
}
while(u!=v){
//이제 깊이가 같아졌기 때문에 동시에 올려주기
u = parent[u];
v = parent[v];
}
return u;
}
int main(){
scanf("%d", &N);
for(int i = 0; i <= N; ++i) depth[i] = -1;
depth[1] = 0; // root 노드 깊이
for(int i = 0, a, b; i< N-1 ; ++i){
scanf("%d %d",&a,&b);
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1);
scanf("%d",&M);
for(int i = 0, a, b; i < M; ++i){
scanf("%d %d", &a, &b);
printf("%d\n", LCA(a, b));
}
return 0;
}
만약 LCA 쿼리 수가 적다면 위처럼 구해도 무관할 것입니다. 하지만 만약 LCA를 구하고자 하는 쿼리가 많다면 시간제한 내에 LCA를 구하기가 어려울 수도 있습니다. 이를 위해 더 효율적인 알고리즘인 O(logN)만에 LCA를 구할 수 있는 방법을 알아보겠습니다.
2. O(logN) 알고리즘
O(logN)만에 LCA를 구할 수 있는 방법도 살펴보겠습니다.
첫 번째 방법과 알고리즘은 매우 유사하나, 노드가 트리를 타고 올라가는 방법에 차이가 있습니다.
- 만약 15칸을 거슬러 올라가야 한다면 어떻게 올라가야 더 빠르게 올라갈 수 있을까요?
- 8칸 → 4칸 → 2칸 → 1칸
- 2의 제곱 형태로 거슬러 올라가도록 하면 O(logN)의 시간 복잡도를 보장할 수 있습니다.
- 즉, 각 노드에 2ⁿ번째 부모 노드 정보를 저장하여 그 정보를 이용하면서 문제를 해결하면 됩니다.
그럼 위의 방법을 적용한 알고리즘을 살펴보겠습니다.
[알고리즘]
1. 트리를 구성할 때 DFS를 통해 각 노드에 자신의 2ⁿ번째 부모 노드와 자신의 깊이를 저장합니다. 이때, 부모 노드의 정보를 저장하는 2차원 배열(par)을 준비합니다. par[x][n]는 i번째 노드의 2ⁿ 번째 부모 노드를 저장합니다.
2. 두 정점 u, v의 깊이가 같은지 확인하고 두 정점의 깊이가 다르다면 두 정점의 깊이가 같아질 수 있도록 2의 제곱 형태로 올라가면서 맞춰 줍니다.
3. 두 정점 u, v의 깊이가 동일하다면, 이제 두 정점이 공유하는 부모 노드 중 깊이가 가장 깊은 부모 노드를 찾아야 합니다. 이는 두 정점이 같이 2의 제곱만큼씩 트리를 타고 올라가면서 두 정점이 만나는 지점으로 구할 수 있습니다. (그 지점이 바로 우리가 구하고자 하는 LCA입니다.)
이해를 돕기 위해서 그림으로 위 알고리즘을 적용해 보겠습니다.
아래와 같은 트리가 있을 때 LCA를 구하고자 하는 두 정점을 1번 방법과 동일하게 6번, 8번으로 정했습니다. 이 때 모든 노드에는 이미 부모 노드의 정보가 저장되어 있다고 합시다. (DFS를 돌린 후의 모습)
그림의 복잡성을 낮추기 위해 6, 8번 노드의 부모 노드 정보만 표시해 보았습니다.
이제 8번 노드를 2의 거듭제곱만큼 올려보겠습니다. 8과 6은 깊이가 1 밖에 차이 나지 않으므로 2⁰만큼 올려 보냅니다.
이제 두 정점의 깊이가 같아졌으므로 동시에 올려 보낼 것입니다. 이때 최대한 2의 거듭제곱만큼 뛰어 올라가도록 합니다. 두 노드가 올라갈 수 있는 최대 깊이는 2이므로 2¹만큼 올려 보내면 한 번에 최소 공통 부모 노드인 1을 찾을 수 있습니다.
위 알고리즘을 코드로 구현하기 전에 par 배열에 대해서 좀 더 살펴보겠습니다. par 배열을 이용하여 아래와 같이 점화식을 세울 수 있습니다.
par[x][n] = par[par[x][n-1]][n-1]
즉 x의 2ⁿ번째 조상은 par[x][n-1]의 2^(n-1) 번째 조상과 같습니다. 예를 들어, n = 4일 때, x의 16번째 조상은 x의 8번째 조상의 8번째 조상(=16번째 조상)과 같습니다.
또한, 두 정점 u, v의 깊이를 맞춰줄 때 어떻게 올릴 것인지 알아보겠습니다. 먼저 두 깊이의 차이(diff)를 구하고, 그 차이가 0이 될 때까지 깊이가 깊은 노드를 뛰게 할 것입니다.
점프를 2의 x제곱만큼 뛰게 할 것이니, 이 점프의 길이를 2진수로 나타낼 수 있습니다. 초반에 간단하게 15칸을 8칸 + 4칸 + 2칸 + 1칸으로 나타내었습니다. 즉, 15는 2진수로 1111 이므로 2⁰, 2¹, 2², 2³ 점프를 해주면 됩니다.
만약 11칸이라면, 2진수로 1011이므로, 2⁰, 2¹, 2³ 씩 점프를 해주면 됩니다. (현재 2진수의 2번째 자리가 0을 나타내므로 여기서는 뛰지 않고 넘어가는 것을 알 수 있습니다.)
따라서 diff가 0이 될 때까지 (깊이 차이가 없을 때까지) diff를 1만큼 오른쪽으로 shift 하여 현재 보고 있는 자리(이진수에서 i번째 자리)가 1이면 2ⁱ칸을 뛰고, 그렇지 않다면 뛰지 않게 만듭니다.
위 사실을 이용하여 코드로 구현해 보겠습니다. 아래 코드는 백준 LCA2(11438번: LCA 2 (acmicpc.net))를 바탕으로 작성되었습니다.
#include<stdio.h>
#include<vector>
#define MAX 100000
#define SWAP(x,y) x^=y^=x^=y
using namespace std;
int par[MAX + 1][17];
int depth[MAX + 1];
vector<int> tree[MAX + 1];
int N, M, maxSize;
void dfs(int cur) {
for (int next : tree[cur]) {
if (depth[next] == -1) { // 아직 방문하지 않은 점
par[next][0] = cur; // next의 2^0번째(=1번째) 부모는 cur
depth[next] = depth[cur] + 1; // next의 깊이는 부모 cur보다 +1
dfs(next);
}
}
}
void initLCA() {
for (int i = 1; i < maxSize; ++i) {
for (int cur = 2; cur <= N; ++cur) {
par[cur][i] = par[par[cur][i - 1]][i - 1];
}
}
}
int LCA(int u, int v) {
if (depth[u] < depth[v]) SWAP(u, v); // 깊이가 얕은 곳의 정점을 v로 설정
int diff = depth[u] - depth[v];
for (int i = 0; diff != 0; ++i) {
// u를 v가 있는 깊이까지 올려주기
if (diff % 2 == 1)
u = par[u][i];
diff >>= 1; //diff /= 2; 오른쪽으로 쉬프트
}
if (u != v) {
//이제 깊이가 같아졌기 때문에 동시에 올려주기
for (int i = maxSize-1; i >= 0; --i) {
if (par[u][i]!=0 && par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
}
u = par[u][0];
}
return u;
}
int main() {
scanf("%d", &N);
for (int i = 0; i <= N; ++i) depth[i] = -1;
depth[1] = 0; // root 노드 깊이
for (int i = 0, a, b; i < N - 1; ++i) {
scanf("%d %d", &a, &b);
tree[a].push_back(b);
tree[b].push_back(a);
}
int tmp = N;
while (tmp > 0) {
maxSize += 1; // 트리 깊이 구하기
tmp >>= 1;
}
dfs(1);
initLCA();
scanf("%d", &M);
for (int i = 0, a, b; i < M; ++i) {
scanf("%d %d", &a, &b);
printf("%d\n", LCA(a, b));
}
return 0;
}