LCA 구현 (Lowest Common Ancestor)

LCA 구현하는 과정을 최대한 간단하게 정리해본다.

---

LCA 는 가장 가까운 공통 조상을 찾는 알고리즘인데,

두 노드에서 한 칸씩 이동하며 찾을 수도 있지만 2의 n제곱 칸씩 이동하며 찾는 방법도 가능하여 시간을 많이 단축할 수 있다.

 

먼저 필요한 자료구조는 다음과 같다.

- depth[node] : node의 루트 노드로부터의 깊이, lca에서 두 노드의 깊이 차이를 구할 때 필요

- parent[node][k] : node의 2^k 번째 부모의 노드 번호, lca에서 두 노드의 공통 조상을 찾을 때 필요

 

과정은 다음과 같다.

1. dfs() 로 depth[node] 와 parent[node][0] (직계 부모)를 구한다.

2. build() 로 parent[node][1..maxlog] 를 구한다. k-1만 있다면 k 값을 구할 수 있다.

3. lca 에서 두 노드의 깊이 차이 diff를 구한다.

4. 더 깊은 노드를 diff 만큼 점프시켜 depth를 맞춘다.

5. 같은 깊이의 노드를 같이 점프시키며 가장 가까운 공통 조상 노드를 찾는다.

 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> v[100001];
int parent[100001][17]; // log2(100000) = 16.61 -> 17
int depth[100001];
 
void dfs(int cur, int prev, int dep) {
 
    // cur의 depth와 parent[cur][0] 세팅
    depth[cur] = dep;
    parent[cur][0] = prev;
    
    for (int i=0;i<v[cur].size();i++){
    
        int next = v[cur][i];
        if (depth[next] == -1) {
            dfs(next, cur, dep+1);
        }
    }
}
 
// parent를 세팅한다
void build() {
    for (int k = 1; k < 17; k++) {
        for (int cur = 1; cur <= N; cur++) {
            // 목적지 = 내 목적지의 절반 + 절반으로 부터 절반
            parent[cur][k] = parent[parent[cur][k - 1]][k-1];
        }
    }
}
 
int lca(int a, int b) {
 
    if (depth[a] < depth[b]) {
        int temp = a;
        a = b;
        b = temp;
    }
 
    int diff = depth[a] - depth[b];
    
    // diff 만큼 뛰어서 depth를 맞춘다. 1011 이면 2^0 + 2^1 + 2^3 만큼 점프
    for (int i = 0; diff!=0; i++) {
    
        // 1이면 점프 후 >> 쉬프트
        if (diff % 2 == 1) {
            a = parent[a][i];
        }
        diff /= 2;
    }
 
    if(a == b) return a;
    
    // dpeth를 맞췄으니 같이 뛴다.
    // 가장 가까운 공통 부모를 찾아야 하므로 parent[a][i] == parent[b][i] 일 때는 스킵
   for(int i=16; i>=0; i--) {
       if(parent[a][i] != -1 && parent[b][i] != -1 && parent[a][i] != parent[b][i]) {
           a = parent[a][i];
           b = parent[b][i];
       }
   }
// 직계 후손의 부모 리턴
    return parent[a][0];
}
 
int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    // -1로 초기화
    memset(depth,-1,sizeof(depth));
    memset(parent,-1,sizeof(parent));
    
    /*
        vector로 관리한다면 아래와 같이 초기화... 
        vector<vector<pii>> v;
        vector<vector<int>> parent;
        vector<int> depth;
        
        v.resize()
           depth.resize(n, -1);
        parent.resize(n, vector<int>(maxlog, -1));
    */
    
    
    //
    
    // 그래프 만들기
    ...
    
    // 
    
    dfs(0,-1,0); // 루트 노드를 0으로 잡는다.
    build();
 
    // lca를 수행한다
    int ret = lca(a,b);
    
    return;
}

 

 

- 어떻게 parent[a][i] != parent[b][i] 일 때 계속 점프하면 최소 공통 조상의 직계 후손이 a가 될까?

만약 최소 공통 조상 x가 2^k 이면 2^k-1은  1111.. 이기 때문에 남은 점프를 모두 하면 직계 후손에 도착.

2^k-1이 아니면, x-1은 1011과 같이 0이 섞여있는데, 1011 -> 011 -> 11 -> 1 에서

2^2와 같이 0인 경우에 점프하면 공통 조상(최소가 아니어도)에 도달하기 때문에 스킵하고 결국 직계 후손에 도착한다.