최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상(LCA)란?

LCA란 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v거나 v의 조상인 노드들 중 가장 깊은 노드이다

 

예를들어, 아래의 트리에서 노드 4와 3의 LCA는 1번 노드이다

다른 예로는 노드 9, 14의 LCA는 2번 노드이며, 노드 3, 13의 LCA는 3번 노드이다

여기서 한가지 사실을 알 수 있는데 노드 u,v와 이들의 LCA w의 관계이다

u,v의 최단 경로는 u-w-v 형태라는 것이다

이를 아래의 트리에서 빨간 경로로 확인할 수 있다

 

 

따라서, 트리 문제에서 최단경로를 빠르게 찾길 원한다면 가장먼저 LCA를 생각해봐야 한다

 

LCA 구현 방법

1. 노드 u,v 가 서로 만날때까지 부모노드를 따라서 두 노드를 옮겨 보는 방법 : 선형 탐색

• 두 노드의 높이가 같은 경우, 가리키는 정점이 같아질 때까지 부모 노드로 거슬러 올라가면 된다

  • 

    정점 4와 7의 LCA를 찾는 경우

• 두 노드의 높이가 다를 경우, 높이를 맞춰주고 나서 하나씩 올리는 방식으로 최악의 경우 O(N)의 시간을 가진다

  • 

    정점 14와 8의 LCA를 찾는 경우

 

구현 코드(c++) : 백준 11437 LCA 

https://www.acmicpc.net/problem/11437

11437번: LCA

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 50002

using namespace std;

int N, M;
vector<int> edge[MAX];
int parent[MAX] = {0,};
int level[MAX] = {0,};

int lca(int u,int v);
void init_tree(int cur, int pre);

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    while(--N){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    init_tree(1,0); // initialize tree
    
    cin >> M;
    while(M--){ // find out LCA for u and v
        int u, v;
        cin >> u >> v;
        cout << lca(u,v) << '\n';
    }
}
int lca(int u,int v){
    // if node <u> level is smaller than node <v>,
    // set the node<u> level's higher
    if (level[u] < level[v])
        swap(u,v);
    
    // make level of two nodes to same level
    while(level[u] != level[v])
        u = parent[u];
    
    // backtrace the tree when the pointers points to the same node
    while( u != v){
        u = parent[u];
        v = parent[v];
    }
    return u;
    
}
void init_tree(int cur, int pre){
    // set the tree for DFS
    parent[cur] = pre;
    level[cur] = level[pre] + 1;
    
    for(int i = 0; i < edge[cur].size(); i++){
        int child = edge[cur][i];
        if (child == pre)
            continue;
        init_tree(child, cur);
    }
    
}

 

 

2. 이분탐색으로 LCA 구하기 :O(log(depth))

• 위에서 살펴본 선형 탐색 방법은 구현이 간단하나 트리의 구조에 따라 시간적 측면에서 매우 비효율적이다
• 양쪽 다 크기 N인 트리에서 이분탐색을 사용하면 O(log(depth))만에 두 특정 점점의 LCA를 찾을 수 있음

구현방법

• 부모노드를 나타내는 parent배열을 2차원으로 둔다
• Parent[x][k] = "x번 정점의 2^k번째 조상 노드의 번호"로 둔다
• 이는 x = 13일때 아래와 같이 표현된다
•  

• DFS를 통해 root부터 트리 구성 시, 낮은 깊이의 노드를 반드시 먼저 탐색하므로 다음 식이 성립한다
• Parent[x][k] = Parent[Parent[x][k-1]][k-1]
• 이는 x = 13일때 아래와 같이 표현된다

• 

• 이 경우, 기존의 선형시간에 구하는 방법에서 부모 노드로 거슬러가는 과정을 2의 제곱수만큼 한 번에 건너뛸 수 있다.

구현 코드(c++) : 백준 11438 LCA2

https://www.acmicpc.net/problem/11438

11437번: LCA

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define MAX 100002
#define MAX_N 18

using namespace std;

int N, M;
vector<int> edge[MAX];
int parent[MAX][MAX_N]; // MAX, 2^N == MAX
int level[MAX] = {0,};
int maxlevel;

int lca(int u,int v);
void init_tree(int cur, int pre, int level);

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    while(--N){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    
    maxlevel = (int)floor(log2(MAX));
    init_tree(1,0,1); // initialize tree
    
    cin >> M;
    while(M--){ // find out LCA for u and v
        int u, v;
        cin >> u >> v;
        cout << lca(u,v) << '\n';
    }
}
int lca(int u,int v){
    // find out lca of <u> and <v>, return
    if( u == 1 || v == 1)
        return 1;
    
    // if node <u> level is smaller than node <v>,
    // set the node<u> level's higher
    int tgt = u, cmp = v;
    if (level[u] < level[v])
        swap(tgt,cmp);
    
    // make level of two nodes to same level
    if( level[tgt] != level[cmp])
        for(int i = maxlevel; i >= 0; i--)
            if( level[parent[tgt][i]] >= level[cmp])
                tgt = parent[tgt][i];
    
    // backtrace the tree when the pointers points to the same node
    int lca = tgt;
    if(tgt != cmp){
        for(int i = maxlevel; i >= 0; i--){
            if(parent[tgt][i] != parent[cmp][i]){
                tgt = parent[tgt][i];
                cmp = parent[cmp][i];
            }
            lca = parent[tgt][i];
        }
    }
    return lca;
}
void init_tree(int cur, int pre, int l){
    // set the tree for DFS
    level[cur] = l;
    parent[cur][0] = pre;
    
    for(int i = 1; i <= maxlevel; i++)
        parent[cur][i] = parent[parent[cur][i-1]][i-1];

    
    for(int i = 0; i < edge[cur].size(); i++){
        int child = edge[cur][i];
        if (child == pre)
            continue;
        init_tree(child, cur, l + 1);
    }
    
}