[백준 11438] LCA 2

 

 

 LCA(Lowest Common Ancestor, 최소 공통 조상) 문제. 어제 풀었던 것보다 좀 더 심플한 유형으로, 순수하게 LCA만 쿼리한다. 

 

 노드의 수가 최대 100,000개까지 입력될 수 있고, 쿼리 또한 100,000개까지 들어올 수 있기 때문에, LCA 탐색에는 O(log N)인 알고리즘을 사용해야 한다.

 어제처럼 Sparse Table을 사용하여 풀었는데, Sparse Table을 생성하는 dfs 내부의 로직을 조금 변경했다. 크게 보면 로직은 같은데, 어제의 경우처럼 테이블에 여러 데이터를 저장하는 게 아니므로 좀 더 심플하게 바꿀 수 있었다.

 

 원리는 어제 설명했듯이, LCA를 찾아나갈 때 부모 노드를 통해 일일이 찾아가는 것이 아니라, 각 노드 별로 2^k번째 조상을 모두 저장해 두고 이를 이용해 로그 시간만에 찾아가는 것이다.

 

 그러기 위해서는 먼저 dfs를 통해 Sparse Table을 구축한다. LCA를 찾아내야 하므로, 그때 이용할 depth 배열도 이때 같이 채워준다. 특정 노드의 조상 정보는 본인의 depth를 이용해서 유효한 조상(2^k 값이 depth보다 작거나 같은 경우)만 채우면 되고, 앞서 채워온 Sparse Table의 조상 정보를 통해 쉽게 채울 수 있다.

 만약 테이블 ancestor[노드 번호][조상 인덱스 k]라고 하면, ancestor[n][i] = ancestor[ancestor[n][i-1]][i-1] 이니까 유효한 i 값의 범위만 탐색해 주면 필요한 조상 정보는 모두 채워진다.

 그다음엔 인접 노드들에 대해 dfs를 마저 진행하는데, 자신의 부모 노드(ancestor[n][0])가 아닌 다른 인접 노드들에 대해 dfs를 재귀호출 하되, 호출 전에 Sparse Table에서 인접 노드의 2^0 번째 조상 노드를 본인으로 설정해 줘서 위의 조상 노드 채우는 로직에 지장이 없도록 한다.

 

 Sparse Table의 구축이 끝났다면, LCA를 찾는 로직을 구현한다. 쿼리 대상인 두 노드 중에 깊이가 더 깊은 쪽의 노드를 타고 올라가 얕은 쪽의 노드와 깊이를 맞춰준다. 물론 이 때도, Sparse Table을 이용한다. 이진수를 나타내는 원리와 같은데, 해당 노드의 깊이보다 작거나 같은 2의 거듭제곱 중 가장 큰 값을 찾아 탐색을 시작한다. 그리고 현재 노드의 깊이에서 해당 값만큼 올라갔을 때 쿼리 대상인 다른 노드의 깊이보다 얕지 않은 지 확인하고, 얕다면 탐색 값을 2로 나누어 다시 확인하고 얕지 않다면 현재 노드를 해당 노드로 갱신하고 탐색을 재개한다.

 그렇게 하다 보면 쿼리 대상인 다른 노드와 깊이가 같아진 후에 탐색이 종료된다. 나는 이걸 노드의 깊이 값 - (1을 비트 쉬프트 연산) 하면서 구했는데, 생각해 보니 처음부터 깊이 차이 값을 구해두고 비트 AND와 쉬프트 연산으로 미리 구하는 방법도 있었겠다 싶다.

 

 높이를 맞췄다면 이때 두 노드가 같은지 확인한다, 같다면 애초부터 같은 족보 내에 있던 경우일 것이다. 바로 해당 노드 값을 리턴한다. 아니라면, 이제 LCA를 마저 찾아야 한다.

 여기도 원리는 똑같다. Sparse Table을 이용해 유효한 범위 내의 가장 큰 조상부터 탐색하며 내려온다. 그러다가 2^k번 째 조상이 달라지는 시점에(공통 조상이 아닌 조상을 보유하게 되는 시점), 각각의 노드를 그 조상으로 갱신해 준다. 이후 k값이 점점 줄어들며 결국에는 LCA의 자식 노드들로 갱신된 상태에서 루프가 종료될 것이고, LCA인 부모 노드 값을 리턴해 종료해 준다. 

 

 사실 이건 글로 읽기보단, 직접 그림을 그려보고 구현해 보는 게 더 쉽지 싶다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int ancestor[100001][17];
int depthList[100001];
vector<vector<int> > adjList;

void dfs(int n, int depth) {

    depthList[n] = depth;

    for(int i=1; i<17; i++) {
        if(depth - (1<<i) >= 0) {
            ancestor[n][i] = ancestor[ancestor[n][i-1]][i-1];
        } else {
            break;
        }
    }

    for(int adj: adjList[n]) {
        if(adj != ancestor[n][0]) {
            ancestor[adj][0] = n;
            dfs(adj, depth+1);
        }
    }
}

int lca(int a, int b) {
    if(depthList[a]<depthList[b]) swap(a, b);

    int k = 0;
    while(1<<(k+1) <= depthList[a]) k++;

    for(int i=k; i>=0; i--) {
        if(depthList[a]-(1<<i) >= depthList[b]) {
            a = ancestor[a][i];
        }
    }

    if(a==b) return a;

    for(int i=k; i>=0; i--) {
        if(ancestor[a][i]!=0 && ancestor[a][i] != ancestor[b][i]) {
            a = ancestor[a][i];
            b = ancestor[b][i];
        }
    }

    return ancestor[a][0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int m, a, b;

    cin >> n;
    adjList = vector<vector<int> >(n+1);

    for(int i=0; i<n-1; i++) {
        cin >> a >> b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }

    dfs(1, 0);

    cin >> m;
    for(int i=0; i<m; i++) {
        cin >> a >> b;
        cout << lca(a, b) << "\n";
    }
}