[ BOJ ][JAVA][11437] LCA

www.acmicpc.net/problem/11437

11437번: LCA

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	256 MB	10473	4652	2717	43.493%

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

예제 입력 1

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

예제 출력 1

2
4
2
1
3
1

코드

/*
    LCA (Lowest Common Ancestor): 최소 공통 조상
    depth를 모두 구하고 부모 자식 간에 관계를 구하여 트리를 만든 다음에
    구하고자 하는 정점의 depth를 맞춰준 다음 같은 노드가 될 때까지 부모를 타고 하나씩 올라오면 된다.
*/
import java.io.*;
import java.util.*;

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

        // 트리 생성
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list.get(u).add(v);
            list.get(v).add(u);
        }

        parent = new int[n + 1];
        depth = new int[n + 1];

        // 루트노드 1, depth 1을 시작으로 각 정점들의 depth를 구한다.
        dfs(1, 1);

        m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            int ret = lca(u, depth[u], v, depth[v]);
            System.out.println(ret);
        }
    }

    // dfs가 아닌 bfs로 각 노드의 depth를 구해도 된다.
    // depth 및 부모 관계 설정
    static void dfs(int from, int cnt) {
        depth[from] = cnt++;
        for (int next : list.get(from)) {
            // depth가 0이 아니면 이미 depth를 구한 노드이다.
            if (depth[next] != 0) continue;

            dfs(next, cnt);
            parent[next] = from;
        }
    }

    // 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;
    }
}