[알고리즘] LCA(최소 공통 조상)

LCA(최소 공통 조상)이란?

 

두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘이다.

 

동작 과정

 

1. 최소 공통 조상을 찾을 두 노드를 확인한다.

2. 먼저 두 노드의 깊이를 같게 만들기 위해 깊이가 더 큰 쪽이 작은 쪽의 깊이에 맞게 거슬러 올라간다.

3. 부모가 같아질 때까지 계속 거슬러 올라간다.

4. 이 과정을 계속 반복해준다.

 

알고리즘 사례

 

예를 들어, 이러한 트리가 있다고 가정하자,

 

이 때, 트리의 노드들의 깊이는 각각 다음과 같다.

 

6번 노드와 10번 노드의 LCA를 구해보자.

 

 

두 노드의 깊이가 각각 2와 3으로 같지 않으므로 두 노드의 깊이를 맞춰주는 작업을 진행해준다.

 

두 노드의 깊이가 같아졌다면 이제 두 노드가 같아질 때까지 거슬러 올라가준다.

 

6번 노드와 10번 노드의 최소 공통 조상이 2라는 걸 확인할 수 있다.

 

아래의 링크에 LCA 기본 알고리즘 문제의 풀이가 있다.

https://kimmessi.tistory.com/230

 

 

각 노드를 거슬러 올라갈 때, 한 칸 씩만 올라간다면 노드의 깊이가 엄청 크다면 시간복잡도는 그에따라 더 커질 것이다.

그렇기 때문에 한 칸 씩 올라가기보다 $2^n$번 째 부모 노드들을 기록해서  $2^n$만큼 올라갈 수 있다면 시간복잡도는 log 만큼 시간복잡도가 더 작아질 것이다.

 

이러한 방식의 예로, 

 

 

3번 노드와 11번 노드의 최소 공통 조상을 구할 때, 노드의 깊이를 같게 만들어주기 위해

 

이렇게 노드의 부모 노드를 $2^i$씩 배열에 저장해주고, $2^i$만큼 거슬러 올라가준다.

 

아래 링크는 위와 같은 방식으로 LCA를 구현한 문제 풀이이다.

https://kimmessi.tistory.com/231

 

 

처음의 방식대로 푼다면 부모노드까지 올라가는데 $O(N)$만큼의 시간복잡도가 요구된다.

따라서 모든 M개의 쿼리를 수행할 때의 시간복잡도는 $O(MN)$이라는 것을 알 수 있다.

 

개선된 방식대로 푼다면 부모노드까지 올라가는데 $O(\mathrm{log} N)$이 요구되고,

따라서 시간복잡도는 $O(M \mathrm{log} N)$이다.

 

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

int N, M;
const int MAX = 100000;

vector<int> tree[MAX+1];
int parent[MAX+1][18], depth[MAX+1];
bool visited[MAX+1];

void set_tree(int cur, int d){
    visited[cur] = true;
    depth[cur] = d;

    for (int i=0;i<tree[cur].size();i++){
        int next = tree[cur][i];

        if(!visited[next]){
            parent[next][0] = cur;
            set_tree(next, d+1);
        } 
    }
}

void dp_parent(int n){
    for(int i=1;i<18;i++){
        for(int j=1;j<=N;j++){
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
}

int LCA(int a, int b){

    if(depth[a] > depth[b]) swap(a, b);

    for(int i=17;i>=0;i--){
        if(depth[b] - depth[a] >= (1 << i)){
            b = parent[b][i];
        }
    }

    if(a == b) return a;

    for(int i=17;i>=0;i--){
        if(parent[a][i] != parent[b][i]){
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main(){
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    cin >> N;

    int a, b;
    for(int i=0;i<N-1;i++){
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }


    set_tree(1, 0);
    dp_parent(N);

    cin >> M;

    for(int i=0;i<M;i++){
        cin >> a >> b;
        
        cout << LCA(a, b) << '\n';
    }

}

위의 코드는 개선된 LCA 문제 풀이 소스 코드이다.

 

 

void set_tree(int cur, int d){
    visited[cur] = true;
    depth[cur] = d;

    for (int i=0;i<tree[cur].size();i++){
        int next = tree[cur][i];

        if(!visited[next]){
            parent[next][0] = cur;
            set_tree(next, d+1);
        } 
    }
}

 

이 함수는 트리의 부모와 노드의 깊이를 저장해주는 함수이다.

DFS로 풀어주면 된다. BFS로 풀어주어도 상관은 없다.

 

void dp_parent(int n){
    for(int i=1;i<18;i++){
        for(int j=1;j<=N;j++){
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
}

 

이 함수는 저장되어있는 부모들을 바탕으로 $2^i$번 째 부모노드들을 배열에 기록해주는 함수이다.

j의 $2^i$번 째 노드는 j의 $2^{i+1}$번 째 노드의 $2^{i+1}$라는 점화식으로 다이나믹 프로그래밍을 해주면 된다.

 

int LCA(int a, int b){

    if(depth[a] > depth[b]) swap(a, b);

    for(int i=17;i>=0;i--){
        if(depth[b] - depth[a] >= (1 << i)){
            b = parent[b][i];
        }
    }

    if(a == b) return a;

    for(int i=17;i>=0;i--){
        if(parent[a][i] != parent[b][i]){
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

 

최종적으로 LCA를 구해주는 함수이다.

깊이가 더 큰 노드를 b로 놓고, b와 a의 깊이차가 같아질 때까지 $2^i$만큼 올라가준다.

 

그리고 여기서 a의 $2^i$번째 부모와 b의 $2^i$번째 부모가 다르다면 그만큼 계속 올라가주고,

 

마지막에는 최소공통조상의 자식노드들이 나오기 때문에 리턴해줄 때는 a의 부모를 리턴해주어야한다.