[백준OJ] 3584번 가장 가까운 공통 조상

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

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

---

 

풀이

DP가 없는 LCA(Lowest Common Ancestor) 알고리즘을 이용하여 문제를 해결했다. N값이 10000으로 작기때문에 DP없이 올라가더라도 시간안에 들었다.

 

먼저, 처음 세팅으로 모든 노드의 깊이를 0으로, 부모를 자기 자신으로 셋팅을 해준다.

그런뒤 입력을 모두 받고, 트리를 만들어 주며 부모-자식 관계를 저장해주었다.

다음으로 모든 노드를 돌며 부모가 자기자신인 노드를 찾아 루트노드로 지정을 해준다음, dfs를 이용해서 루트노드부터 깊이를 설정해준다.

 

깊이를 다 구해주었으면, LCA를 구하고싶은 노드를 두개 입력받은뒤, 해당 노드들의 깊이가 같을때까지, 더 깊은 노드를 위로 올려준다. 이때 같은 깊이까지 올렸을때 같은노드라면, 그 노드가 LCA가 되는것이고, 같지않다면, 부모가 같아질때까지 두 노드를 동시에 한칸씩 올려준다. 그런뒤 부모가 같다면, 그 노드가 LCA가 되는것이다.

 

시간복잡도

2ⁱ번째 부모를 구한뒤 문제를 해결하는 방식이아닌, 한칸한칸 거슬러올라가는 간단한 LCA를 사용했기때문에, DFS에 O(N), LCA를 구할때 O(N)이 걸리므로, 총 O(N)이 된다.

 

코드

#include<iostream>
#include<vector>

using namespace std;

vector<int> maze[10001];
int depth[10001]={0};
int parent[10001]={0};

void make_depth(int now,int pa){
    depth[now]=depth[pa]+1;
    for(int next:maze[now]){
        if(next!=pa){
            make_depth(next,now);
        }
    }
}

int main() {
	
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<=n;i++){
            maze[i].clear();
            depth[i]=0;
            parent[i]=i;
        }
        for(int i=0;i<n-1;i++){
            int to,from;
            cin>>to>>from;
            maze[to].push_back(from);
            parent[from]=to;
        }
        int root=0;
        for(int i=1;i<=n;i++){
            if(parent[i]==i) root=i;
        }
        parent[root]=0;
        make_depth(root,0);
        int a,b;
        cin>>a>>b;
        
        if(depth[a]>depth[b]){
            int temp=a;
            a=b;
            b=temp;
        }
        while(depth[b]!=depth[a]){
            b=parent[b];
        }
        if(a==b){
            cout<<a<<"\n";
        }
        else{
        
            while(parent[a]!=parent[b]){
                a=parent[a];
                b=parent[b];
            }

            cout<<parent[a]<<"\n";
        }
    }
    
	return 0;
}