[ BOJ 백준 11437번 - LCA ] 해설 및 코드

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

 

 

목적

트리에서 두 정점이 주어질 때, 최소 공통 조상을 찾자.

 

접근법

1. 트리에서 정점의 부모와 깊이를 배열에 저장하고, 입력으로 주어지는 정점의 깊이를 동일하게 한 뒤, 동시에 위로 올라가면서 부모가 같은지 비교한다.

 

#include<iostream>
#include<vector>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int t[50000][2];
vector<int> m[50000];
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    while(--n){
        int a,b;cin>>a>>b;
        m[a].push_back(b);
        m[b].push_back(a);
    }
    t[1][0]=t[1][1]=1;
    int q[50000]={1},l=0,r=1;
    while(l!=r){
        int i=q[l++],len=m[i].size();
        f(j,0,len)if(t[m[i][j]][0]==0){
            t[m[i][j]][0]=i;
            t[m[i][j]][1]=t[i][1]+1;
            q[r++]=m[i][j];
        }
    }
    
    int m;cin>>m;
    while(m--){
        int a,b;cin>>a>>b;
        if(a==1||b==1) a=1;
        else{
            while(t[a][1]<t[b][1])b=t[b][0];
            while(t[b][1]<t[a][1])a=t[a][0];
            while (a!=b)a=t[a][0],b=t[b][0];
        }
        cout<<a<<'\n';
    }
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.