BOJ 11437 LCA

www.acmicpc.net/problem/11437

11437번: LCA

LCA 문제이다. (Lowest Common Ancestor )

 

사실 이 문제에 대한 최적화 방안은 한창 알고리즘을 공부할 때 같이 스터디를 하는 형한테서 들었지만, 따로 구현은 해보지 않았었다. 

처음 이 문제를 접한다면 다들 똑같은 생각을 할 것이다. (물론 나도 처음에는 같은 생각을 했었다.)

"시작 node들로부터 depth가 같은 ancestor 까지 탐색을 진행 한 뒤, 방금 구한 ancestor들 부터 같은 node가 나올 때 까지 탐색을 진행한다"

 

하지만, 이 문제를 까다롭게 하는 것은 Query의 수이다.

위의 생각대로 구현을 한다면 시간복잡도  O(n) 이 걸리고, Query 수가 총 m개이므로 해당 문제의 시간복잡도는 O(nm) 이 된다.

 

이 상황을 해결할 수 있는 것은 탐색시간을 줄이는 것으로,

첫째, 한칸 한칸씩 올라가며 탐색하는 것이 아니라, 처음에는 1칸, 다음에는 2칸, .... , n 번째에는 2^n 칸을 탐색하는 것으로 시간을 O(n) 에서 O(log n) 으로 줄일 수 있다.

둘째, 이를 사용하기 위해서는 2^n 번째 조상이 저장되어 있는 배열이 하나 필요하다.

ancestor [node][n]가 node의  2^n번째 조상을 저장하고 있다고 할 때

해당 배열의 점화식은 다음과 같다.

ancestor [node][n] = ancestor[ ancestor[ node ][ n-1 ] ][ n-1 ]   

점화식의 의미는 "2^n 번째 조상 node는  2^(n-1) 번째 조상 node의  2^(n-1) 번째 조상 node와 같다." 이다.

 

자세한 설명이 필요하다면 다른 갓갓 분들이 쓰신 블로그를 참조하거나 추후 올릴 포스트를 참조하시면 될 것 같다.

 

 

첫번째 사항과 두번째 사항을 생각하며 구현한다면 다음과 비슷하게 나올 것이다. (아래 코드는 내가 제출한 코드이다.)

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m;
int ancestor[50001][30];
int depth[50001];
vector<vector<int>> graph;

int lca(int a, int b){
    if(depth[a] < depth[b])
        swap(a,b);
    int sub = depth[a] - depth[b];
    int power = 0;

    while(sub){
        int t = sub%2;
        sub /= 2;
        if(t != 0)
            a = ancestor[a][power];
        power += 1;
        //안올라가는줄 알았는데 왜 올라가야하지
    }
    while(a != b){
        power = 0;
        while(ancestor[a][power] != ancestor[b][power]){
            power += 1;
        }
        if(power > 0)
            power -= 1;
        a = ancestor[a][power];
        b = ancestor[b][power];
    }
    return a;
}

void make_ancestor(){

    //BFS로 짰는데, DFS로 짜면 더 짧아질 것 같음
    bool visited[50001] = {false,};
    int d = 0;
    queue<int> q;
    q.push(1);
    depth[1] = 0;
    
    while(q.size()){
        int qsize = q.size();
        for(int i=0;i<qsize;i++){
            int now = q.front();
            visited[now] = true;
            q.pop();
            for(int next : graph[now]){
                if(!visited[next]){
                    ancestor[next][0] = now;
                    depth[next] = depth[now]+1;
                    q.push(next);
                }
            }
        }
    }

    for(int index = 1;index<30; index++){
        int t = 0;
        for(int i=2;i<=n;i++){
            ancestor[i][index] = ancestor[ancestor[i][index-1]][index-1];
            t += ancestor[i][index];
        }
        if(!t) 
            break;
    }
}


int main(){
    
    scanf("%d",&n);
    graph.resize(n+1);
    for(int i=0;i<n-1;i++){
        int a, b; scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    make_ancestor();

    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int a, b; scanf("%d%d",&a,&b);
        printf("%d\n", lca(a,b));
    }

    return 0;
}