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

 

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

 

 

 

 

 

LCA(Lowest Common Ancestor) 알고리즘을 사용하여 최소 공통 조상을 구하는 문제이다. 하나의 쌍에 대한 LCA를 구하면 되기 때문에 문제풀이 원리는 아래 LCA 설명 링크로 대신하고 전체 코드만 기록해두겠다.

 

LCA 개념 및 구현 방법

[알고리즘] 최소 공통 초상(LCA)

 

 

 

 

 

 

 

 

 

 

전체 코드

import java.io.*;

public class Main {
	
    public static void main (String[] args) throws IOException {
        new Main().solution();
    }
    
    
    int N, parent[];
    
    private void solution () throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = {};
        
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            
            N = Integer.parseInt(br.readLine());
            
            // 노드간의 부모 - 자식 관계를 저장하는 배열
            parent = new int[N+1];
            
            for (int i = 0; i < N-1; i++) {
                input = br.readLine().split(" ");
                int p = Integer.parseInt(input[0]);
                int c = Integer.parseInt(input[1]);
                parent[c] = p;
            }
            
            
            input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            
            System.out.println(LCA(root, u, v));
        }
        
        
        br.close();
    }
    
    
    // 특정 노드로부터 루트 노드까지 거슬러 올라가 깊이를 반환
    private int calDepth (int node) {
        
        int depth = 0;
        
        // parent[루트노드] == 0 이므로 현재 노드와 루트 노드간의 깊이 차이를 구할 수 있다.
        while (parent[node] != 0) {
            node = parent[node];
            depth++;
        }
        
        return depth;
    }
    
    
    private int LCA (int u, int v) {
        
        int u_depth = calDepth(u);
        int v_depth = calDepth(v);
        
        // 두 노드 중 깊이가 더 깊은 노드를 findCommonParent의 첫 번째 인자로 전달한다.
        if (u_depth > v_depth) 
            return findCommonParent(u, v, u_depth-v_depth);
        else 
            return findCommonParent(v, u, v_depth-u_depth);
    }
    
    
    private int findCommonParent (int u, int v, int interval) {
    	
        // 두 노드의 깊이를 깊이가 얕은 노드의 깊이로 통일시킨다.
    	while (interval-- > 0) 
    		u = parent[u];
    	
        // 두 노드의 첫 공통 부모를 찾을 때까지 깊이를 줄이며 탐색
    	while (u != v) {
    		u = parent[u];
    		v = parent[v];
    	}
    	
    	return u;
    }
}