[알고리즘]#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. 깊이 목록 + 조상 노드 목록 초기화

#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

#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

 

// 예제

 

---