[BOJ/백준][Gold4] 3584 : 가장 가까운 공통 조상 (C++)

https://www.acmicpc.net/problem/3584

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

 

[난이도] Gold4
[유형] LCA

[풀이]
1. 공통 조상을 찾아야 하는 두 노드의 깊이를 구한다.
2. 깊이가 더 깊은 노드를 깊이 차이만큼 부모로 보내 깊이를 맞춰준다.
3. 깊이가 같아진 두 노드를 부모로 보내는 것을 반복하면서 두 노드가 같아지면
그 노드가 공통 조상이다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,N,par[10001],rt,p1,p2;
int getH(int n){
    int ret=0,cur=n;
    while(cur!=rt){
        cur=par[cur];
        ret++;
    }
    return ret;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        memset(par,0,sizeof(par));
        for(int i=1;i<N;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            par[b]=a;
        }
        scanf("%d%d",&p1,&p2);
        for(int i=1;i<=N;i++){
            if(par[i]==0) {
                rt=i;
                break;
            }
        }
        int p1h=getH(p1),p2h=getH(p2);
        if(p1h<p2h) {
            swap(p1,p2);
            swap(p1h,p2h);
        }
        for(int i=0;i<p1h-p2h;i++) p1=par[p1];
        while(p1!=p2){
            p1=par[p1];
            p2=par[p2];
        }
        printf("%d\n",p1);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/3584.cpp