[Java] LCA (Lowest Common Ancestor)

https://pangtrue.tistory.com/262

[백준 11438 : JAVA] LCA 2 / 최소 공통 조상

0. 깊이 초기화

dfs를 통해 parent[a][0] 을 각자 초기화 (부모노드의 번호)

 

1. parent 배열 초기화

- parent[a][b] : a번 노드에서 2^b 만큼 위의 노드 번호

 

2. 2^i 씩 위로 올리는 테크닉

- 1) 비교할 두 노드 중 더 깊은 노드를 위로 올려 높이를 맞춤

- 2) 2^i 씩 위로 올릴 경우 같은지? 를 체크해서 log로 탐색

 

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

public class g3_11437 {
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int n, dep = 0;
    static List<List<Integer>> list = new ArrayList<>();
    static int[] deps;
    static int[][] parents;

    public static void main(String[] args) {
        n = fs.nextInt();
        for (int i=0;i<=n;i++) list.add(new LinkedList<>());
        for (int i=0;i<n-1;i++){
            int a = fs.nextInt(), b = fs.nextInt();
            list.get(a).add(b);
            list.get(b).add(a);
        }

        int temp = 1;
        while (temp < n){
            temp *= 2;
            dep++;
        }

        parents = new int[n + 1][dep];
        deps = new int[n + 1];
        dfs(1, 1);
        fill();

        int t = fs.nextInt();
        while (t-- > 0){
            int a = fs.nextInt(), b = fs.nextInt();
            if (deps[a] < deps[b]){
                temp = a;
                a = b;
                b = temp;
            }

            for (int i=dep-1;i>=0;i--){
                if (Math.pow(2, i) <= deps[a] - deps[b]){
                    a = parents[a][i];
                }
            }

            for (int i=dep-1;i>=0;i--){
                if (parents[a][i] != parents[b][i]){
                    a = parents[a][i];
                    b = parents[b][i];
                }
            }

            if (a == b) pw.println(a);
            else pw.println(parents[a][0]);
        }

        pw.close();
    }

    static void fill(){
        for (int i=1;i<dep;i++){
            for (int j=1;j<=n;j++){
                parents[j][i] = parents[parents[j][i - 1]][i - 1];
            }
        }
    }

    static void dfs(int node, int depth){
        deps[node] = depth;
        for (Integer i : list.get(node)){
            if (deps[i] == 0){
                dfs(i, depth + 1);
                parents[i][0] = node;
            }
        }
    }

    // ----------input function----------

    static void sort(int[] a) {
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a)
            L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++)
            a[i] = L.get(i);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}