LCA(Lowest Common Ancestor) / 최소 공통 조상 알고리즘

LCA(Lowest Common Ancestor) /  최소 공유 조상

목차

1. LCA란?

2. O(N) LCA 알고리즘

3. O(logN) LCA 알고리즘

 

LCA란?

LCA란 말 그대로 최소 공유 조상이다. 그래프에서 두 노드 각각의 부모들을 쭉 타고 올라갔을 때 최초로 공유하는 부모를 말한다. 

 

이 예시에서 노드 5와 노드 3의 최초 공유 조상은 1이 된다. 

 

이 경우에 노드 12와 노드3의 최소 공유 조상은 1이 된다.

 

 

O(N) LCA 알고리즘

자 그러면 이제 LCA 알고리즘을 구현해 봅시다. 

LCA 구현을 위해 3가지 단계가 필요합니다.

• 각 노드들의 depth를 구하여 가지고 있는다 ( depth : root 노드부터 자기 노드까지의 거리(깊이))
• LCA를 구하려는 두 노드 중 더 깊은 노드의 depth를 더 낮은 노드의 depth로 맞춘다.
• 이후 두 노드를 같이 한칸씩 parent를 찾아가며 동일한 부모(LCA)가 나올 때 까지 찾는다.

위의 예시로 설명해 보겠습니다.

 

예시1

1. 각 노드들의 depth를 구하기

=> dfs를 한번 돌려서 전처리 하면 모든 노드의 depth를 구할 수 있습니다.

 

2. LCA를 구하려는 두 노드 중 더 깊은 노드의 depth를 더 낮은 노드의 depth로 맞춘다.

노드 5의 depth 는 2 / 노드3의 depth는 1입니다. 5번의 depth가 3번 보다 크므로(깊으므로), 5번의 depth가 3번의depth와 같아질 때 까지 5번을 부모를 찾으며 끌어 올려줍니다. 그러면 노드 2번이 됩니다.

=> 노드 5번을 노드2번으로 업데이트 합니다.

 

3. 이후 두 노드를 같이 한칸씩 parent를 찾아가며 동일한 부모(LCA)가 나올 때 까지 찾는다.

노드 2번, 노드 3번의 부모를 올려가며 탐색하면 최초로 나오는 부모가 1번입니다. 따라서 노드 5번과 노드3번의 LCA는 1이 되겠네요.

 

예시2

1. 각 노드들의 depth를 구하기

 

2. LCA를 구하려는 두 노드 중 더 깊은 노드의 depth를 더 낮은 노드의 depth로 맞춘다.

노드 12의 depth가 4, 노드 3의 depth가 1이므로, 노드 4를 depth가 1이 될 때 까지 부모를 찾으며 올려줍니다. ( 2번 노드가 되겠네요)

3. 이후 두 노드를 같이 한칸씩 parent를 찾아가며 동일한 부모(LCA)가 나올 때 까지 찾는다.

2번 노드와 3번 노드의 최초 공유 부모를 찾으면 1번이 됩니다. 즉 LCA는 1번 입니다

 

이 알고리즘이 왜 O(N)일까요,

부모를 찾아 올라가는 과정에서 최악의 경우 전체 노드의 개수만큼 탐색하여 올라가야 하기 때문입니다.

최악의 경우라하면 노드들이 일자로 연결되어 있는 경우입니다.

 

최악의 경우O(N)

 

백준 문제 :

www.acmicpc.net/problem/11437

11437번: LCA

소스코드

#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
int par[50001];//부모 노드를 저장
int depth[50001];
vector<int> tree[50001];
bool visited[50001];
 
void dfs(int n) {//DFS를 통해 부모노드, depth를 탐색
    visited[n] = true;
 
    for (int i = 0; i < tree[n].size(); i++) {
        int now = tree[n][i];
        if (!visited[now]) {
            par[now] = n;
            depth[now] = depth[n] + 1;
            dfs(now);
        }
    }
}
int main() {
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int x, y;
        cin >> x >> y;
        tree[y].push_back(x);
        tree[x].push_back(y);
    }
    dfs(1);
    
    cin >> M;
    while (M--) {
        int a, b;
        cin >> a >> b;
        if (depth[a] < depth[b]) swap(a, b);//편의상 더 깊이가 깊은 쪽을 a로 설정
        while (depth[a] != depth[b]) a = par[a];//depth가 같아질때 까지 부모노드로 업데이트
        while (a != b) {//공통 부모 찾기
            a = par[a];
            b = par[b];
        }
        cout << a << '\n';
    }
}

 

O(LogN) LCA 알고리즘

위의 방식대로 풀게 되면 노드N * 쿼리 M인 경우  O(N*M)으로 시간초과가 나는 경우가 있습니다.

그래서 더 효율적인 알고리즘을 생각해야 합니다. 

방법을 한마디로 정의하자면, 공통부모를 찾아 올라가는 과정을 2^n으로 더 빠르게 뛰어올라가며(?) 찾는 것입니다. 

 

이를 위해서는 자신의 2^n번째 부모를 알고 있어야 합니다. 

par[n][i]를 정의한다. par[n][i]는 노드n의 2^i번째 부모입니다.

 

par[n][0]은 위의 방법에서 부모를 찾았던 방식을 동일하게 이용하면 됩니다.(DFS)

이제 점화식으로 남은 2^i 번째 부모를 채워야합니다. 

점화식은 다음과 같습니다. 

par[n][i] = par[par[n][i-1]][i-1];

n의 2^i-1번째 부모의(par[n][i-1]) 2^i-1번째 부모가 n의 2^i번째 부모입니다. 

 

이후 방법은 동일합니다. 

다만 우리는 2^i번째 부모를 알고 있으므로 더 빠르게 뛰어가듯! 공통 조상을 찾을 수 있습니다.

 

- 두 노드의 깊이를 맞춰줄 때 ( 한 쪽의 깊이가 더 깊을 때)

앞서 한칸 씩 깊이를 올려가던 과정을 이제는 2^i씩 올려가면서 깊이가 같아지도록 맞춤.

 

- 두 노드의 깊이를 맞춰 준 후, 공통 조상을 구할 때도 마찬가지로 2^i씩 올려가면서 깊이가 같아지도록 맞춤.

 

백준 문제 : 

www.acmicpc.net/problem/11438

11438번: LCA 2

 

소스코드

#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
int par[100001][21];//부모 노드를 저장
int depth[100001];
vector<int> tree[100001];
bool visited[100001];
 
void dfs(int n) {//DFS를 통해 부모노드, depth를 탐색
    visited[n] = true;
 
    for (int i = 0; i < tree[n].size(); i++) {
        int now = tree[n][i];
        if (!visited[now]) {
            par[now][0] = n;
            depth[now] = depth[n] + 1;
            dfs(now);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int x, y;
        cin >> x >> y;
        tree[y].push_back(x);
        tree[x].push_back(y);
    }
    dfs(1);
    
    for(int j = 1; j < 17 ; j++){
        for (int i = 1; i <= N; i++) {
            int tmp = par[i][j - 1];
            par[i][j] = par[tmp][j - 1];
        }
    }
    cin >> M;
    while (M--) {
        int a, b;
        cin >> a >> b;
        if (depth[a] < depth[b]) swap(a, b);//편의상 더 깊이가 깊은 쪽을 a로 설정
        int gap = depth[a] - depth[b];
        for (int i = 20; i >= 0; i--) {
            if (gap >= (1 << i)) {
                gap -= (1 << i);
                a = par[a][i];
            }
        }
        //a와 b의 깊이차이를 2^i씩 올리면서 맞춰줌
 
        if (a == b) {
            cout << a << '\n';
            continue;
        }
        else {
            for (int i = 20; i >= 0; i--) {
                if (par[a][i] != par[b][i]) {
                    a = par[a][i];
                    b = par[b][i];
                }
            }//a, b의 공통 조상을 찾아 나감. 이 때도 2^i씩 올리면서 업데이트
            cout << par[a][0] << '\n';
        }
        
    }
}