[백준 3584] 가장 가까운 공통 조상 (Java)

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

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

1. 주의할 점

- LCA 알고리즘에 대해 알고 있어야 한다

- O(NlgN)에 수행되는 알고리즘을 이해하도록 한다

 

2. 구현

- 모든 변에 대해 입력받은 후, havePar[] 배열을 통해 트리의 Root를 찾는다

- DFS() 함수를 통해 각 Node의 트리에서 높이를 구한다

- Make_tree() 함수를 통해 N번째 Node의 2^i번째 높이에 위치한 조상들을 갱신한다

A의 2^i번째 조상: B
B의 2^i번째 조상: C
-> A의 2^i+1번째 조상
-> B의 2^i번째 조상
-> C
위의 원리를 이용한 갱신

- find_lca() 함수를 통해 넘겨받은 두 노드의 공통조상을 Return한다. 설명은 주석을 통해 이해하면 된다

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int depth[],par[][];     //각 노드의 높이(루트: 0), par[i][N]: N의 2^i번째 높이만큼 위에 있는 Node값(Ex. i==0: 바로 위 부모를 가리킴)
    static int node,root;
    static List<Integer> li[];
    static int havePar[];
    
    static void make_tree(){
        for(int i=0;i<15;i++)
            for(int j=1;j<=node;j++)
                if(par[i][j]!=-1)
                    par[i+1][j] = par[i][par[i][j]];
    }
    
    static void dfs(int num, int level){
        depth[num]=level;
        for(int i=0;i<li[num].size();i++){
            int next = li[num].get(i);
            if(depth[next]==-1){
                par[0][next]=num;
                dfs(next,level+1);
            }
        }
    }
    
    static int find_lca(int c, int p){
        if(depth[c]<depth[p]){
            int temp = p;
            p=c;
            c=temp;
        }
        int diff = depth[c]-depth[p];
        
        //더 하단에 있는 노드를 DP를 통해 P의 높이에 맞추는 과정
        for(int i=0;diff>0;i++,diff/=2){
            if(diff%2==1) c = par[i][c];
        }
        
        //공통 부모가 같지 않다면
        if(c!=p){
            //공통 부모 바로 밑까지 구한다
            for(int i=14;i>=0;i--){
                if(par[i][c]!=-1 && par[i][c]!=par[i][p]){      //2^i만큼 위로 올렸을 때, 부모가 있으며 + 둘다 2^i만큼 올렸는데 부모가 다르다면 -> 우선 그만큼 올린다
                    c = par[i][c];
                    p = par[i][p];
                }
            }
            //위의 조건에서 부모가 있으며, 부모가 같은 경우에 공통조상으로 갱신을 안했으므로 여기서 수행
            c = par[0][c];
        }
        return c;
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String ss = br.readLine();
	    StringTokenizer st = new StringTokenizer(ss);
	    int test = Integer.parseInt(st.nextToken());
	    int child=0,parent=0;
	    
    	for(int t=0;t<test;t++){
    	    ss = br.readLine();
    	    st = new StringTokenizer(ss);
    	    node = Integer.parseInt(st.nextToken());
    	    
    	    //초기화
    	    depth = new int[node+1];
    	    par = new int[15][node+1];
    	    li = new List[node+1];
    	    havePar = new int[node+1];
    	    for(int i=1;i<=node;i++)
    	        li[i] = new ArrayList<>();
    	    for(int a[]:par)
    	        Arrays.fill(a,-1);
    	    Arrays.fill(depth,-1);
    	    
    	    for(int i=0;i<node;i++){
    	        ss = br.readLine();
        	    st = new StringTokenizer(ss);
        	    int a = Integer.parseInt(st.nextToken());
        	    int b = Integer.parseInt(st.nextToken());
        	    if(i==node-1){
        	        child = a;
        	        parent = b;
        	        break;
        	    }
        	    li[a].add(b);
        	    havePar[b]++;
    	    }
    	    //루트 찾기
    	    for(int i=1;i<=node;i++){
    	        if(havePar[i]==0){
    	            root=i;
    	            break;
    	        }
    	    }
    	    dfs(root,0);
    	    make_tree();
    	    System.out.println(find_lca(child,parent));
    	}
	}
}