[Algorithm] 최소 공통 조상 LCA (Lowest Common Ancestor)

최소 공통 조상이란?

 

 

최소 공통 조상(LCA)란 두 노드가 트리에서 두 노드를 포함하여 조상을 따라 거슬러 올라갈때 처음 공통으로 만나게 되는 정점이다.

 

아래 그림에서 5와 8의 LCA 는 바로 1이다.

 

 

 

 

 

 

 

그럼 어떻게 임의의 두 노드에 대해서 처음으로 같이 만나는 조상을 찾을 수 있을까?

 

처음으로 생각해 볼 수 있는 방법은 서로 만날 때까지 부모 노드를 따라서 두 노드를 옮겨 보는 것이다. 두 노드의 높이가 다르다면 높이를 맞춰주고 나서 하나씩  올려본다면  트리의 깊이를 H 라했을 때 찾는데 O(H)가 되고 최악의 경우 O(N) 의 시간을 가지게 된다.

 

더 빠르고 효율적으로 하는 방법은 없을까?

 

 

DP 배열을 이용해서 O(logN) 시간에 구할 수 있다.

 

만약 두 노드의 15번째 조상이 서로 다르다면 1,2,3...,15 번 비교를 하나하나 다하지말고 한 번에 15번째로 바로 건너가자.

 

모든 노드의 2^K 번째 조상을 모두 기록해놓고 찾는 아이디어이다.

 

DFS 로 트리를 순회하며 모든 정점의 Depth 를 기록해 둔다.(두 노드의 높이가 다르다면 맞춰줘야하기 때문에)

 

DP 배열 A[V][K] 에 V번 정점의 2^K 번 째 부모 정점 번호를 기록해둔다.

 

A[V][0] 은 해당 V 노드의 부모 노드, 즉 1번째 조상이다. 이 부분은 DFS 를 돌면서 미리 저장해둔다.

 

A[V][K] = A[A[V][K-1]] [K-1] 로 나타낼 수 있다.

 

해당 DP 배열을 채울 때 K에 해당하는 루프를 바깥쪽으로 꺼내줘야 하는데 그 이유는 다음과 같다.

 

만약 K 루프를 안쪽에다 넣었을 경우

 

A[1][1] = A[A[1][0]] [0];

A[1][2] = A[A[1][1]] [1];

A[1][3] = A[A[1][2]] [2];

 

이런식으로 채워지게 되는데 A[1][1] 값은 구할 수 있지만 우리는 아직 A[A[1][1]] [1] 값은 알지 못한다. A[A[1][1]] [0] 값은 DFS 통해서 알고 있는 상태이다.

 

따라서 조상을 2^0 조상을 다채우고 2^1 조상을 다채우고 .... 이런식으로 가야 모든 배열값을 올바르게 구할 수 있다.

 

A[2][1] = A[A[2][0]] [0];

A[3][1] = A[A[3][0]] [0];

 

이런식으로 구해야한다.

 

 

 

X,Y 의 LCA를 구한다하면 LCA(X,Y) 의 구현은

 

① X와 Y의 높이가 같다면 높이를 하나씩 올려본다.

② X와 Y의 높이가 다르다면 높이를 맞춰준다.

③ 같아 지는 조상을 찾는다.

 

 

 

아래 문제는 https://www.acmicpc.net/problem/11438 (LCA2) 문제이며 LCA를 구해보는 기본 문제이다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M;
int dep[100001];
int A[100001][21];
int visit[100001];
vector <int> edge[100001];
 
 
int LCA(int X, int Y) {
 
 
    if (dep[X] != dep[Y]) {
        if (dep[X] > dep[Y]) { swap(X, Y); } // x 가 작은 수 y 가 큰 수
 
        for (int i = 20; i >= 0; i--) {
            if (dep[Y]-dep[X] >= (1<<i)) {  // (1<<i) 가 높이이다.
                Y = A[Y][i];
            }
        }
    } // dept 를 같게 만들어줌.
 
    if (X == Y) return X;
    
 
    if (Y != X) {
        for (int i = 20; i >= 0; i--) {
            if (A[X][i] != A[Y][i]) {
                X = A[X][i];
                Y = A[Y][i];
            }
        }
    }
 
    return A[X][0]; // 최소 공통 조상 리턴
 
}
void dfs(int n, int d, int dad) {
 
    dep[n] = d;
    d++;
 
    for (int i = 0; i < edge[n].size(); i++) {
        if (dad == edge[n][i]) continue;
 
        A[edge[n][i]][0] = n;
        dfs(edge[n][i], d, n);
    }
}
 
int main() {
 
    scanf("%d", &N);
 
 
    for (int i = 0; i < N - 1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    //dep[1] = 0;
 
    A[1][0] = 0;
    dfs(1, 0, 0);
 
    
 
    for (int y = 1; y <= 20; y++) { //DP 배열 생성
        for (int x = 1; x <= N; x++) {
            A[x][y] = A[A[x][y - 1]][y - 1];
        }
    }
 
    
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int X, Y; scanf("%d %d", &X, &Y);
        printf("%d\n", LCA(X, Y));
    }
 
 
 
    return 0;
}