[알고리즘]#7_LCA(Least Common Ancestor)

#1. 개념

 

1. LCA(Least Common Ancestor)

 

LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘을 효율적으로 구현하는 방법으로 Binary Lifting 기법이 있습니다.

 

2. Binary Lifting 기법

 

출저 : https://iq.opengenus.org/binary-lifting-k-th-ancestor-lowest-common-ancestor/

 

Binary Lifting 기법은 주어진 트리 자료구조에서 두 노드의 LCA를 찾는 방법 중 하나입니다. 특히, Binary Lifting 기법은 깊이가 깊은 트리에서 두 노드의 LCA를 찾는데 효율적입니다. BL의 핵심 개념은 각 노드에 대해 미리 점프할 수 있는 조상 정보를 계산해 두고, 이를 이용해 두 노드의 LCA를 찾는 것입니다. Binary Lifting을 활용한 LCA 알고리즘의 사전 처리 과정은 O(n log n) 시간 복잡도 + 두 노드의 LCA를 찾는 과정은 O(log n)의 시간 복잡도를 가지며, 특히 여러 LCA 쿼리를 처리해야 하는 경우에 매우 효율적입니다. 다만, 사전 처리 과정에서 각 노드의 조상 정보를 저장할 추가적인 메모리 공간이 필요합니다.

 

3. 동작 방식

 

1. 깊이 목록 + 부모 노드 목록 초기화 (노드 개수 적을 때)

// BFS로 각 노드의 깊이와 부모 찾기
void bfs(int root) {
    vector<bool> visited(N, false);
    queue<int> q;

    depth[root] = 0;
    visited[root] = true;
    q.push(root);

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        for(int next : graph[cur]) {
            if(!visited[next]) {
                depth[next] = depth[cur] + 1;
                parent[next] = cur;
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

일반적으로, DFS 혹은 BFS를 통해 부모 목록을 찾고, 깊이 목록을 작성합니다.

 

2. 깊이 목록 + 조상 노드 목록 초기화 (Binary Lifting 적용, 깊이가 깊을 경우)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5; // 최대 노드 수
const int LOG = 20; // 2^20 = 1048576, MAXN보다 큰 가장 작은 2의 제곱수의 로그 값
int ancestor[MAXN][LOG]; // up[v][j]는 v로부터 2^j 위에 있는 노드
int depth[MAXN]; // 루트로부터의 깊이
vector<int> graph[MAXN]; // 그래프 인접 리스트

// DFS를 사용하여 각 노드의 조상 노드 정보 업데이트
void dfs(int v, int p) {
    ancestor[v][0] = p; // v의 바로 위 부모는 p
    for (int i = 1; i < LOG; ++i) {
        if (ancestor[v][i-1] != -1) ancestor[v][i] = ancestor[ancestor[v][i-1]][i-1]; // v로부터 2^i 위에 있는 노드 계산
        else ancestor[v][i] = -1;
    }
    for (int u : graph[v]) {
        if (u == p) continue; // 부모 노드는 건너뜀
        depth[u] = depth[v] + 1; // 깊이 업데이트
        dfs(u, v); // 재귀적으로 자식 노드 탐색
    }
}

int main() {
    // 그래프 구성 및 사전 처리 로직
    // 루트 노드를 시작점으로 하는 dfs 호출, 루트 노드의 부모 노드는 -1
	dfs(1, -1)

    return 0;
}

LCA 알고리즘을 수행하기 전에 Binary Lifting 기법을 활용하여 각 노드의 조상 노드 정보를 계산하는 사전 처리 과정을 수행합니다. 먼저, 각 노드의 조상 노드 정보를 기억할 2차원 벡터 혹은 배열이 필요합니다. 2차원 배열의 row는 현재 노드를 의미하며, col은 현재 노드로부터 2^col(2의 col승) 위에 위치한 노드를 의미합니다. DFS를 수행하며, 각 노드의 조상 정보 + 깊이 정보를 업데이트해줍니다. 

 

2. LCA 

 

1. 일반 버전

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;  // 최대 노드 수
vector<int> graph[MAXN];  // 그래프 인접 리스트
vector<int> parent;  // 각 노드의 부모 노드
vector<int> depth;  // 루트로부터의 깊이

// DFS를 사용한 부모와 깊이 계산
void dfs(int curr, int prev) {
    parent[curr] = prev;  // 현재 노드의 부모 저장
    
    for(int next : graph[curr]) {
        if(next != prev) {  // 부모 노드가 아닌 경우에만
            depth[next] = depth[curr] + 1;  // 깊이 설정
            dfs(next, curr);  // 재귀적으로 자식 노드 탐색
        }
    }
}

// 두 노드의 LCA 찾기
int lca(int a, int b) {
    // 항상 a가 더 깊은 노드가 되도록
    if(depth[a] < depth[b]) {
        swap(a, b);
    }
    
    // 깊이 맞추기
    while(depth[a] > depth[b]) {
        a = parent[a];
    }
    
    // 같은 깊이에서 같은 노드가 될 때까지 위로 올라가기
    while(a != b) {
        a = parent[a];
        b = parent[b];
    }
    
    return a;  // LCA 반환
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;  // 노드 수
    cin >> n;
    
    // 벡터 크기 초기화
    parent.resize(n);
    depth.resize(n);
    
    // 트리 입력 받기 (n-1개의 간선)
    for(int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 루트(0)부터 시작하여 각 노드의 부모와 깊이 계산
    depth[0] = 0;
    dfs(0, -1);  // 루트의 부모는 -1
    
    // 쿼리 처리
    int q;  // 쿼리 수
    cin >> q;
    
    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    
    return 0;
}

 

2. Binary Lifting 적용 버전

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5; // 최대 노드 수
const int LOG = 20; // 2^20 = 1048576, MAXN보다 큰 가장 작은 2의 제곱수의 로그 값
int ancestor[MAXN][LOG]; // up[v][j]는 v로부터 2^j 위에 있는 노드
int depth[MAXN]; // 루트로부터의 깊이
vector<int> graph[MAXN]; // 그래프 인접 리스트

// DFS를 사용한 사전 처리
void dfs(int v, int p) {
    ancestor[v][0] = p; // v의 바로 위 부모는 p
    for (int i = 1; i < LOG; ++i) {
        if (ancestor[v][i-1] != -1) ancestor[v][i] = ancestor[ancestor[v][i-1]][i-1]; // v로부터 2^i 위에 있는 노드 계산
        else up[v][i] = -1;
    }
    for (int u : graph[v]) {
        if (u == p) continue; // 부모 노드는 건너뜀
        depth[u] = depth[v] + 1; // 깊이 업데이트
        dfs(u, v); // 재귀적으로 자식 노드 탐색
    }
}

// 두 노드의 LCA 찾기
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b); // a가 더 깊은 노드로 설정
    // 깊이 맞추기
    for (int k = LOG - 1; k >= 0; --k) {
        if (depth[a] - (1 << k) >= depth[b]) {
            a = ancestor[a][k];
        }
    }
    if (a == b) return a; // 깊이를 맞춘 후 같은 노드라면 그 노드가 LCA
    // 공통 조상 찾기
    for (int k = LOG - 1; k >= 0; --k) {
        if (ancestor[a][k] != ancestor[b][k]) {
            a = ancestor[a][k];
            b = ancestor[b][k];
        }
    }
    return ancestor[a][0]; // 최종적으로 위로 한 칸 올라간 노드가 LCA
}

int main() {
    // 그래프 구성 및 사전 처리 로직
    // 예: dfs(루트노드, -1);
    // LCA 쿼리 예시: cout << lca(노드1, 노드2) << endl;

    return 0;
}

 

다음으로, 주어진 두 노드에 대하여 LCA를 수행합니다. LCA 알고리즘은 작은 5단계로 구성됩니다.

1) 주어진 두 노드 u, v에 대하여 상대적으로 깊이가 더 깊은 정점을 미리 설정한다.
2) 두 노드 u, v의 깊이 값을 비교하고, 그 값이 최소가 되도록 맞춰준다.
3) u, v가 같은 노드라면, 이를 반환하고 종료한다.
4) u, v가 서로 다른 노드라면, 부모 노드를 2^i씩 점프하며 올라가며 LCA를 찾는다.
5) u, v가 서로 같은 부모를 가지게 되었을 때, ancestor[a][0]을 반환한다.

 

---

 

#3. 예제

 

1. LCA

 

2. LCA w/ Binary Lifting

 

// 예제

 

---