백준 11437번 : LCA[java]

1. 각 노드에 인접한 모든 노드를 저장한다(edge)

2. edge를 바탕으로 각 노드들의 높이와 부모노드를 구한다.

3. 입력받은 n1과 n2중 더 깊은 노드를 위로 올리면서 같은 높이로 맞춘다.

4. 두 노드에서 한 칸씩 위로 올라가며 비교하는 것을 공통 조상이 나올 때 까지 반복한다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main{
	static ArrayList<ArrayList<Integer>> edge = new ArrayList<>();
	static int[] parents; // parents[i] = i의 부모
	static int[] height; // height[i] = 트리에서 i의 깊이
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        parents = new int[N+1];
        height = new int[N+1];
        for(int i=0; i<=N; i++) {
        	edge.add(new ArrayList<Integer>());
        }
        for(int i=0; i<N-1; i++) {
        	String[] str = br.readLine().split(" ");
        	int n1 = Integer.parseInt(str[0]);
        	int n2 = Integer.parseInt(str[1]);
        	edge.get(n1).add(n2);
        	edge.get(n2).add(n1);
        }
        
        int root = 1;
        parents[root] = -1;
        FindHeight(1,edge.get(1),1);
        
        int T = Integer.parseInt(br.readLine());
        while(T-->0) {
        	String[] str = br.readLine().split(" ");
        	int n1 = Integer.parseInt(str[0]);
        	int n2 = Integer.parseInt(str[1]);
        	
        	// n1보다 n2가 더 깊도록 설정해두고
        	if(height[n1] > height[n2]) {
        		int temp = n1;
        		n1 = n2;
        		n2 = temp;
        	}
        	
        	// n1과 같은 높이가 될 때 까지 n2의 높이를 올립니다.
        	while(!(height[n1] == height[n2])) {
        		n2 = parents[n2];
        	}
        	
        	int LCA = -1;
        	// 같은 높이에서부터 n1과 n2가 한 칸씩 올라가며 같아지는 순간을 찾습니다.(최소 공통 조상)
        	while(!(n1==n2)) {
        		n1 = parents[n1];
        		n2 = parents[n2];
        	}
        	LCA = n1;
        	
        	System.out.println(LCA);
        }
    }

    static public void FindHeight(int p, ArrayList<Integer> children, int h) {
    	for(int i=0; i<children.size(); i++) {
    		int c = children.get(i);
    		if(parents[c] == 0) {
    			parents[c] = p;
    		}
    		if(c != parents[p]) {
        		height[c] = h;
        		FindHeight(c,edge.get(c),h+1);
    		}
    	}
    }
}