BOJ 3584 Nearest Common Ancestors

 

문제 링크 : https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

주어진 문제는 root 가 주어진 tree 에서 최소(?)의 공통 조상을 찾기를 요구하는데...

 

노드(정점) 집합의 크기로 보아 lca(least comman ancestor) 와 관련된 기술을 쓰지 않아도 될 것으로 보인다.

하지만 분류상 '최소공통조상'에 들어 있는 문제이니, 하라는 대로 했다.

 

각 노드가 자신의 부모만 알고 있으면 모든 조상을 찾을 수 있는 것은 당연하다.

할아버지는 부모의 부모이니 할아버지를 찾으려면 부모한테 물어보면 된다.

하지만 이래서야 한참 선대 조상을 찾는데 시간이 너무 걸린다.

그렇다고 모든 조상의 정보를 가지고 있기에는 메모리가 문제가 될 것이다.

 

그래서 늘 그렇듯이 \( \log n\) 타협이 등장한다. 2 의 거듭제곱 선조들만 알고 있겠다는 뜻.

ance[i][k] 는 i 번 노드의 \(2^k\) 번째 조상을 뜻한다.

우선 깊이 우선 탐색으로 각자의 부모를 기록해 둔다. 

\(1=2^0\) 이므로 부모는 틀림없이 2 의 거듭제곱 선조에 해당한다.

 

 

(위의 dfs 는 각자의 부모만이 아니라 각 노드의 깊이도 기록한다.)

그리고 다음 함수를 이용해서 \(2^k\) 번째 조상을 기록한다.

 

 

최초에 부모(\(2^0\) 번째 조상) 만 알고 있었지만 부모의 부모인 \(2^1\) 번째 조상(할아버지) 을 알수 있다.  

다시 이를 토대로 할아버지의 할아버지, 즉 \(2^2\) 번 조상을 찾을 수 있다. 

 

그럼 2 의 거듭제곱이 아닌 조상은?

예를 들어 3 대 조상을 찾고 싶다. \(3=11_{2}\) 이므로 부모에서 2 대 조상을 찾으면 된다.

그럼 7 번째 조상은? \(7=111_{2}\) 니까 먼저 부모를 찾아 다시 \(6=110_2\) 대를 거슬로 올라간다.

끝이 \(10_2\) 이므로 2대를 올라가고 다시 \(4=100_2\)대를 거슬러 가면 된다.

 

 

여기서 i 는 2진법 자리수에 대응된다.

증가할 때마다 2 의 거듭제곱에 해당되는 크기로 조상을 거슬러 올라간다.

 

각 부분들은 대충 설명했으니 전체 코드를 보자.

 

#include<bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> adj, ance;
vector<int> level;

void dfs(int cur, int prv){
    level[cur]=level[prv]+1;
    ance[cur][0]=prv;
    
    for(auto nxt:adj[cur])
        if(!level[nxt])
            dfs(nxt, cur);
}

void func(){
    for(int k=1;k<15;k++)
        for(int i=1;i<=n;i++)
            ance[i][k]=ance[ance[i][k-1]][k-1];
}

int lca(int u, int v){
    if(level[u]<level[v]) swap(u,v);
    int d=level[u]-level[v];
    
    for(int i=0; d>0; i++, d>>=1){
        if(d%2) u=ance[u][i];      
    }
    
    if(u==v) return u;
    
    for(int i=14;i>=0;i--){
        if(ance[u][i]==ance[v][i])
            continue;
        u=ance[u][i], v=ance[v][i];
    }
    
    return ance[u][0];
}

void solve(){
    scanf("%d", &n);
    adj=vector<vector<int>>(n+1);
    ance=vector<vector<int>>(n+1, vector<int>(15));
    level=vector<int>(n+1);
    
    vector<int> cnt(n+1);
    for(int i=0;i<n-1;i++){
        int u,v; scanf("%d%d",&u,&v);
        cnt[v]++;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    
    int root=-1;
    for(int i=1;i<=n;i++)
        if(!cnt[i]) {
            root=i;
            break;
        }
    
    dfs(root,0);
    func();
    
    int a,b; scanf("%d%d",&a,&b);
    printf("%d\n", lca(a,b));
}

int main(){
    int T; scanf("%d", &T);
    while(T--) solve();
}

 

root 를 찾는 과정. 이 문제에서는 간선을 u v 로 줄 때 앞의 u 가 부모이고 v 가 자식이다.

root 는 누구의 자식도 아니므로 v 자리에 등장하는 번호를 카운트해서 0 인 것이 root 이다. (다른 노드는 누군가의 자식이므로 반드시 한 번 이상 v 자리에 등장한다.)

 

노드의 개수가 10000 개 이하니까 \(2^{14}\) 을 초과하는 조상은 없어서 14 가 등장한다.