[ BOJ ][JAVA][3584] 가장 가까운 공통 조상

www.acmicpc.net/problem/3584

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

문제

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

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

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

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

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

예제 입력 1

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

예제 출력 1

4
3

코드

/*
    가장 가까운 공통 조상
    LCA 알고리즘 (최소 공통 조상)
    - 만약 트리의 루트가 한 루트로 고정되어 있다면 dfs를 통해 탐색할 수 있다. (BOJ 11437)
    - 루트가 정해져 있지 않다면 아래에서 위로 올라가는 방식을 이용하면된다.
*/
import java.io.*;
import java.util.*;

public class p3584 {
    static int t, n;
    static int[] parent;
    static List<List<Integer>> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            n = Integer.parseInt(br.readLine());
            list = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                list.add(new ArrayList<>());
            }
            parent = new int[n + 1];

            // 트리 생성 및 부모관계 생성
            for (int i = 0; i < n - 1; i++) {
                st = new StringTokenizer(br.readLine());
                int p = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                parent[c] = p;
                list.get(p).add(c);
            }

            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            int uDepth = getDepth(u);
            int vDepth = getDepth(v);

            int same = lca(u, uDepth, v, vDepth);
            System.out.println(same);
        }
    }

    // LCA 알고리즘 
    static int lca(int a, int aDepth, int b, int bDepth) {
        // 두 노드의 depth가 같아질 때까지 한쪽을 올린다.
        if (aDepth > bDepth) {
            while (aDepth != bDepth) {
                aDepth--;
                a = parent[a];
            }
        } else if (aDepth < bDepth) {
            while (aDepth != bDepth) {
                bDepth--;
                b = parent[b];
            }
        }
        // 두 노드의 높이를 같게 했다.

        // 그 이후에 depth를 똑같이 증가시키다가 (내 윗 부모가 되는 것이 올라가는 과정)
        // 만난 같은 정점이 가장 가까운 공통 조상이 된다.
        while (a != b) {
            a = parent[a];
            b = parent[b];
        }

        return a;
    }

    static int getDepth(int x) {
        int ret = 0;
        int cur = x;
        while (cur != 0) {
            ret++;
            cur = parent[cur];
        }

        return ret-1;
    }
}