[백준/JAVA] BOJ 3584 - 가장 가까운 공통 조상

가장 가까운 조상을 찾아 보자

👀 문제

3584번: 가장 가까운 공통 조상 ✨ 골드 4

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Ancestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

예제 입력

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

예제 출력

4
3

🔑 키포인트

트리 최소 공통 조상

✍️ 코드

1️⃣ 비효율적인 첫 번째 방법
🤔 문제 내 노드의 수가 최대 10,000개라서 통과는 되지만 노드가 늘어나게 되면 시간이 너무 오래 걸림 O(N) 이렇게 풀지 맙시다

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

public class BOJ3584_가장가까운공통조상 {
    static int[] parent;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()); // 노드의 수
            parent = new int[n + 1];
            visited = new boolean[n + 1];
            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());
                parent[b] = a;
            }
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            find(n1);
            sb.append(closest(n2) + "\n");
        }
        System.out.print(sb.toString());
    }

    static void find(int a) {
        if (!visited[a]) {
            visited[a] = true;
            if (parent[a] == 0) { // root
                return;
            }
            find(parent[a]);
        }
    }

    static int closest(int b) {
        if (visited[b]) {
            return b;
        } else {
            return closest(parent[b]);
        }
    }
}

2️⃣ 두 노드의 depth를 맞춘 뒤, 동시에 위로 올려서 처음 만나는 곳을 찾는 방법 ✅

• 입력 트리 구성 및 DFS: O(N)
• 쿼리 1회당 LCA 찾기: O(log N) (depth 차이 만큼만 올라가므로)

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

public class BOJ3584_가장가까운공통조상 {
    static int n;
    static ArrayList<ArrayList<Integer>> tree;
    static int[] parent, depth;
    static boolean[] hasParent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        for (int tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 노드의 수
            tree = new ArrayList<>();
            parent = new int[n + 1];
            depth = new int[n + 1];
            hasParent = new boolean[n + 1];

            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);
                hasParent[b] = true;
            }

            // 루트 찾기
            int root = 1;
            for (int i = 1; i < n + 1; i++) {
                if (!hasParent[i]) {
                    root = i;
                    break;
                }
            }
            dfs(root, 0, 0);

            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            sb.append(lca(n1, n2) + "\n");
        }
        System.out.print(sb.toString());
    }

    static void dfs(int now, int par, int d) {
        parent[now] = par;
        depth[now] = d;
        for (int next : tree.get(now)) {
            dfs(next, now, d + 1);
        }
    }

    static int lca(int n1, int n2) {
        // 깊이 맞추기
        while (depth[n1] > depth[n2]) {
            n1 = parent[n1];
        }
        while (depth[n2] > depth[n1]) {
            n2 = parent[n2];
        }
        // 공통 조상 찾기
        while (n1 != n2) {
            n1 = parent[n1];
            n2 = parent[n2];
        }
        return n1;
    }
}