[C++] 최소 공통 조상( lowest common ancestor, LCA ) 구하기

최소 공통 조상( lowest common ancestor )이란

최소 공통 조상( LCS )은, 그래프에서 선택된 두 정점의 공통된 조상 정점 중에서, 가장 큰 깊이를 가진 정점을 말합니다.

참고로, 노드의 깊이( depth )는 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말합니다.

 

최소 공통 조상

 

위의 그래프에서, 정점 6과 7의 공통 조상은 4, 2, 1번 정점들입니다.

그중에서 깊이가 가장 큰 4번 정점이 최소 공통 조상입니다.

 

이 최소 공통 조상을 구하는 알고리즘은 두 단계로 나눠집니다.

첫 번째, 두 정점의 깊이를 일치시킵니다.

두 번째, 같은 깊이를 가진 두 정점의 트리 경로를 따라 동시에 위로 올라가면서, 처음으로 일치하는 부모를 찾습니다.

이 부모가 LCA가 됩니다.

 

아래의 그래프에서 6번과 10번 정점의 최소 공통 조상을 찾으려면,

 

먼저, 6번과 10번의 깊이를 일치시킵니다.

10번이 6번 보다 깊이가 더 크므로, 10번을 7번으로 올려서, 깊이를 일치시킵니다.

깊이 일치시키기

 

이제, 6번과 7번 정점에서 시작해서, 일치하는 부모가 나올 때까지 위로 올라갑니다.

이렇게 해서, 처음으로 만나는, 일치하는 정점이 최소 공통 조상이 됩니다.

여기서는 4번 정점이 LCS입니다.

최소 공통 조상 찾기

 

이를 구현하기 위해선 먼저, 주어진 그래프에서, 각 정점의 깊이와 바로 위의 부모 정점을 구해야 합니다.

여기서는 너비 우선 탐색( BFS, breath first search ) 방식으로, 정점들을 탐색하여 필요한 정보들을 구합니다.

 

너비 우선 탐색에 관한 내용은 여기에서 볼 수 있습니다.

[백준/BOJ] 24445번: 너비 우선 탐색 2 ( BFS, Breath-First Search ) - C++ 문제 풀이

 

이를 코드로 작성하면 다음과 같습니다.

#define SIZE    100000	// 임의의 정점 개수
#define MAX_LEVEL  17	// 임의의 최대 깊이

vector<int> graph[SIZE+1];	// 주어진 그래프
bool visited[SIZE+1];
int depth[SIZE+1];		// 각 정점의 깊이
int parent[MAX_LEVEL+1][SIZE+1];	// 각 정점의 부모 저장

// 너비 우선 탐색
void BFS( int start){
    
    queue<int> q;

    visited[start] = true;
    
    int next_level = 1; // 노드의 깊이
    int level_size = 1; // 현재 깊이에 있는 정점의 개수
    int cnt = 0;

    q.push(start);

    while( !q.empty()){
        int vert = q.front();
        q.pop();

        for( int x : graph[vert] ){
            if ( !visited[x] ){
                visited[x] = true;
                parent[0][x] = vert;    // 정점 x의 부모 노드 저장
                depth[x] = next_level;  // 정점의 깊이
                q.push(x);
            }
        }

        cnt++;
        if ( cnt == level_size){    // 다음 깊이 단계로 진행
            cnt = 0;
            next_level++;
            level_size = q.size();
        }
    }
}

여기서, parent는 각 정점의 부모 노드를 저장하고 있는 2차원 배열입니다.

왜 parent를 2차원 배열로 작성하는지는 아래에서 다시 설명할 것입니다.

우선은, parent [ 0 ][ x ]에 정점 x의 바로 위의 부모 정점을 저장합니다.

 

이제, 위에서 구한 정보들을 사용하여, 두 정점의 깊이를 일치시킵니다.

// 두 정점을 같은 깊이로 만드는 함수
void MakeSameDepth( int& a, int& b){
    
    if ( depth[a] > depth[b]){
        swap(a, b);
    }

    int diff = depth[b] - depth[a];
    while(diff > 0){
        b = parent[0][b];   // 트리 경로를 따라 위로 이동
        diff--;
    }
}

 

마지막으로,  트리의 root까지 올라가면서, 일치하는 부모 정점을 발견하면 그 정점이 최소 공통 부모( LCA )입니다.

int FindLCA( int a, int b){

    while( a != b){
        a = parent[0][a];	// 트리 경로를 따라 위로 이동
        b = parent[0][b];
    }

    return a;	// 최소 공통 조상
}

 

그런데, 위에서 두 정점의 깊이 차이가 16이라면, 두 정점의 깊이를 일치시키기 위해선, 한 정점을 트리 경로를 따라 16번이나 이동하는 과정을 거쳐야 합니다.

하지만, 이동해야 하는 정점의 16번째 조상을 미리 기록해 둔다면, 한 번에 그 조상 정점으로 이동하여, 두 정점의 깊이를 일치시킬 수 있을 것입니다.

 

마찬가지로, 트리의 높이가 50인 경우, 일치하는 부모를 찾기 위해 최대 49번의 이동과 비교하는 과정이 필요합니다.

하지만, 정점의 조상들을 미리 저장하는 과정을 통해, 이를 더 빠르게 수행할 수 있습니다.

 

그래서, parent 이차원 배열을 사용합니다.

이 배열의 parent [k][n]에는 임의의 노드 n의 $2^k$ 단계 위의 조상 노드를 저장합니다.

그럼, 다음과 같은 값들이 parent 배열에 저장됩니다.

 

우선, parent [0][n]에 정점 n의 바로 위의 부모를 저장합니다. 

( 이 값은 위의 너비 우선 탐색 과정에서 이미 값을 저장해 두었습니다. )

 

그리고, parent [1][n]에는 깊이 2단계 위의 부모를 저장합니다.

예를 들면, 정점 10의 깊이 2단계 위의 부모는 parent [1][10] = 7입니다.

 

2단계 위의 조상의 위치

 

parent [2][n]에는 깊이 4단계 위의 부모를 저장합니다.

정점 10의 깊이 4단계 위의 부모는 parent [2][10] = 3입니다.

이렇게, 2의 배수 조상을 저장함으로써, 빠른 이동이 가능합니다.

 

4단계 위의 조상의 위치

 

이런 식으로 parent 배열을 채워 넣기 위해, 다음의 성질을 이용합니다.

k >= 1 일 때,

parent [k][n] = parent [ k-1 ][ parent [ k-1 ][n] ]

 

이 식이 말하는 것은, 정점 n의 $2^k$ 단계 위의 부모는, n의 $2^{k-1}$ 단계 위의 부모의, 또 $2^{k-1}$ 단계 위의 부모라는 것입니다.

예를 들면, 정점 10의 4단계 위인 parent [2][10]은, 정점 10의 2단계( $2^1$ ) 위의 부모인 7의, 2단계( $2^1$ ) 위의 부모인 정점 3이라는 말이 됩니다.

 

이것을 식으로 계산해 보면 다음과 같습니다.

parent [2][10] = parent [1][ parent [1][10] ] = parent [1][7]이 됩니다.

그리고, parent [1][7] = parent [0][ parent [0][7] ] = parent [0][4] = 3이 됩니다.

 

코드로 작성하면 다음과 같습니다.

int kmax;	// 다른 곳에서도 이 값을 사용하므로 전역으로

void SetupAncestor(int N){	// N은 그래프의 정점 수
    
    kmax = 0;
    int val = 1;
    while( val <= N){
        val <<= 1;  // 두 배씩 세는 수를 증가
        kmax++;
    }

    for( int k = 1; k <= kmax; k++){
        for( int n = 1; n <= N; n++){	// 모든 정점에 대해 부모들을 기록
            parent[k][n] = parent[k-1][ parent[k-1][n] ];
        }
    }
}

여기서, kmax는 $2^k$ >= N를 만족시키는 k의 최소 값입니다.

이 값은, 가장 깊이 있는 노드에서 바로 root까지 이동하는데 필요한 최소 값입니다.

배열의 값을 구해야 할 한계 값이기도 합니다.

 

이제, 두 정점의 깊이를 일치시키는 위의 함수 MakeSameDepth를 아래와 같이 변경합니다.

void MakeSameDepth( int& a, int& b){
    
    if ( depth[a] > depth[b]){
        swap(a, b);
    }

    for( int k = kmax; k >= 0; k--){
        if (pow(2, k) <= depth[b] - depth[a]){
            b = parent[k][b];
        }
    }
}

만약, a와 b의 깊이 차이가 20이라면, b를 우선 16 단계( k = 4 ) 위로 올립니다.

그리고, 다음번에 나머지 4( k = 2 ) 단계를 올려서 둘의 깊이를 일치시킬 수 있습니다.

 

이제, 마지막 FindLCA 함수는 다음과 같이 변경합니다.

int FindLCA( int a, int b){
    
    if ( a == b)	// 이미 일치하면 종료
        return a;

    for( int k = kmax; k >=0; k--){
        if ( parent[k][a] != parent[k][b]){	// 부모가 일치할 때까지 위로 이동
            a = parent[k][a];
            b = parent[k][b];
        }
    }

    int lca = parent[0][a];	// 바로 위의 부모가 LCA
    return lca;
}

위의 for 구문을 통해서, 바로 위의 부모가 일치할 때까지 두 정점을 위로 올립니다.

for 문이 끝나면, 최소 공통 부모( LCA )가 각 정점의 바로 위의 정점이 됩니다.

 

이 알고리즘을 사용해서 문제를 해결하는 글은 여기에서 볼 수 있습니다.

[백준/BOJ] 11438번: LCA 2 ( 최소 공통 조상 구하기 ) - C++ 문제 풀이