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

Lowest Common Ancestor

트리에서 두 정점이 주어질 때 가장 가까운 공통 조상을 찾는 알고리즘
시스템, 생물학 등 다양한 분야에서 활용될 수 있으며, 계층이 있는 구조에서 갈래를 찾는데에 사용이 될 수 있다.

알고리즘

처음 생각한 방법

계층 구조가 확실하다면 해당 정점들의 정보를 통해 루트로 각각 한칸씩 올라간다.
이후 두 정점이 한 칸씩 올라가며 방문한 노드에 다시 방문한 경우 그 정점이 최소 공통 조상이라고 판단

이 방법은 O(N)의 시간 복잡도로 한 번 실행할 때에 나쁘지 않은 방법으로 보였다.

푼 문제 : 3584번가장 가까운 최소 공통 조상
다만 LCA 라는 이름의 문제로 넘어가니 위에서 푼 문제를 쿼리처럼 여러번 사용해야해서 시간 복잡도 O(N) 알고리즘으로는 해결할 수 없었다.

최적화된 방법

시간 복잡도가 O(1) 또는 O(log n)으로 해당 작업을 줄여야 된다고는 인식 했는데 어떻게 해야할 지 잘 모르겠어서 찾아보니 이진 탐색과 비슷한 방식을 사용하는 것을 알게 되었다.

먼저 다음의 방식으로 트리를 저장해주어야 한다.
극단적인 경우를 통해 이해하기 쉽도록 구조를 구성해 보자.

이 처럼 1자형으로 생긴 트리를 가정해 저장 구조를 탐색해보자.
각 노드는 본인의 1칸 높은 조상, 2칸 높은 조상, 4칸 높은 조상 ... 처럼 2의 제곱수만큼 먼 조상을 링크하는 방식을 가진다. 이를 이용한다면 마치 이진탐색처럼 올라가며 두 노드의 공통 조상을 확인할 수 있다.
표로 그 구조를 확인해보자.
표에서 표현 시 루트를 넘어서려는 경우 0으로 저장했다.

vertex	1	2	4	8
1	0	0	0	0
2	1	0	0	0
3	2	1	0	0
4	3	2	0	0
5	4	3	1	0
6	5	4	2	0
7	6	5	3	0
8	7	6	4	0
9	8	7	5	1

이 표에서 패턴이 보인다면 성공적이다.
코드로는 아래처럼 표현할 수 있다.

void dfs(int now, int depth, int p){
    d[now] = depth;
    for(auto i : edge[now]){
        if(i == p)continue;
        parent[i][0]=now;
        dfs(i,depth+1,now);
    }
}

int main(){
    for(int i=1; i<20; i++){
        for(int j=1; j<=n; j++){
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
}

0번은 깊이(depth)를 측정하며 책정하고 1번부터는 메인함수의 2중 반복문으로 나머지를 채운다.
표와 같이 보면 도움이 될 것이다.

이후에는 두 정점의 깊이를 비교하며 깊이를 맞춰준 후 같이 올라가며 이진 탐색으로 문제를 해결해 주었다.

int lca(int a,int b){
    // depth 동일하게 맞춰주기
    while(d[a] != d[b]){
        int diff = max(d[b],d[a]) - min(d[b],d[a]);
        int w = 1,cnt = 0;

        while(w*2 <= diff){
            w*=2;
            cnt++;
        }
        if(d[a] < d[b]){
            b = parent[b][cnt];
        }
        else{
            a = parent[a][cnt];
        }
    }
    // 이진 탐색
    while(a!=b){
        int i = 1;
        while(parent[a][i] != parent[b][i])i++;
        a = parent[a][--i];
        b = parent[b][i];
    }
    return a;
}

관련 문제 - 11438 - LCA 2