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

문제

---

 

 

 

풀이

---

LCA(Lowest Common Acestor_최소 공통 조상) 알고리즘을 사용하는 기본 유형의 문제다.

해당 문제에서 주의깊게 봐둬야할 건 각 노드의 2^i 번 째 조상노드를 테이블에 저장하기 위해 DP를 사용한 점화식이다.

1. DFS 탐색을 통해 각 노드별 depth를 구해 배열에 저장하고, 각 노드의 첫 번째 조상노드를 parent 배열에 담는다. (DP 사전준비)
2. DP 알고리즘을 통해 각 노드의 모든 2^i 번 째 조상노드를 구해 parent 배열에 저장한다.
3. LCA(a, b)에서 a와 b의 깊이를 맞춘 후, 차례로 2^i 번 째 조상노드를 구해가며 최소 공통 조상을 찾는다.

 

위의 2번을 보면 DP를 통해 각 노드의 2^i 번 째 조상노드를 저장한다고 되어 있는데, 해당 코드를 보자.

for (int i = 1; i < depth; i++) {
    for (int j = 1; j <= N; j++) {
        parent[j][i] = parent[ parent[j][i - 1] ][i - 1];
    }
}

 

A 정점의 2^1 번 째 조상은 A 정점의 2^0 번 째 조상노드의 2^0 번 째 조상과 같다.

A 정점의 2^1 번 째 조상노드 = A 정점의 2^0 번 째 조상노드의 2^0 번 째 조상노드

 

 

 

코드

---

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N, M, K;
    private static List<List<Integer>> tree;
    private static int[] depth;
    private static int[][] parents;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        tree = new ArrayList<>();
        for (int i = 0; i < N + 1; i++)
            tree.add(new ArrayList<>());

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree.get(a).add(b);
            tree.get(b).add(a);
        }

        int tmp = 1;
        K = 0;
        while (tmp <= N) { // 최대 depth 알아내기.
            tmp <<= 1;
            K++;
        }

        depth = new int[N + 1];
        parents = new int[N + 1][K];

        dfs(1, 1);
        fillParents();

        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            int lca = lca(a, b);
            bw.write(lca + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int lca(int a, int b) {
        if (depth[a] < depth[b]) { // 깊이가 낮은 쪽을 기준으로 맞춘다.
            int temp = a;
            a = b;
            b = temp;
        }

        //더 깊은 a를 2승씩 점프하며 두 노드의 depth를 맞춘 후, 맞춘 depth의 조상 노드로 대체한다.
        for (int i = K - 1; i >= 0; i--) {
            if (Math.pow(2, i) <= depth[a] - depth[b]) {
                a = parents[a][i]; // a를 2^i 번 째 조상 노드로 대체한다.
            }
        }

        // depth 맞춘 후 대체한 조상 노드가 b와 같다면. 즉, a의 조상노드가 b라면 종료한다.
        if (a == b) return a;

        // 이제 두 노드는 같은 depth를 가지기 때문에
        // 같이 2승씩 점프시키며 공통부모 바로 아래까지 올린다.
        for (int i = K - 1; i >= 0; i--) {
            if (parents[a][i] != parents[b][i]) {
                a = parents[a][i];
                b = parents[b][i];
            }
        }

        return parents[a][0];
    }

    private static void fillParents() {
        for (int i = 1; i < K; i++) { // DP를 이용해 각 노드별 2^K 번 째 조상 노드를 저장한다.
            for (int j = 1; j <= N; j++) {
                parents[j][i] = parents[ parents[j][i - 1] ][i - 1];
            }
        }
    }

    private static void dfs(int node, int cnt) {
        depth[node] = cnt;

        for (Integer next : tree.get(node)) {
            if (depth[next] == 0) {
                dfs(next, cnt + 1);
                parents[next][0] = node;
            }
        }
    }
}