[BOJ]11437 - LCA (G3)

문제 링크

11437-LCA

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다.

그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

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

문제 풀이

LCA 알고리즘 의 기본적인 문제이다.
이미 알고리즘을 알고 있었기때문에 어렵지 않게 해결방향을 정할 수 있었음!

dfs 에서 부모와 깊이에 대한 정보를 초기화해주고
lca 에서 최소공통 조상을 구해낸다.

두 수에 대하여 깊이가 같아질때까지 부모 방향으로 거슬러 올라가고
깊이가 같아진다면 두 수가 같아질때까지 부모 방향으로 거슬러 올라간다.
결국 두 수가 같아진다면 그 수가 최소 공통 조상이다.

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

public class Main {
    static int n, m;
    static ArrayList<Integer>[] tree;
    static int[] parents, depth;

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

        n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n + 1];
        parents = new int[n + 1];
        depth = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<Integer>();
        }

        Arrays.fill(depth, -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());
            tree[a].add(b);
            tree[b].add(a);
        }

        dfs(1, 1, 0);
        m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(lca(a, b) + "\n");
        }
        System.out.println(sb);

    }

    public static void dfs(int cur, int dep, int parent) {
        depth[cur] = dep;
        parents[cur] = parent;

        for (int next : tree[cur]) {
            if (next != parent) {
                dfs(next, dep + 1, cur);
            }
        }
    }

    public static int lca(int a, int b) {
        int aDepth = depth[a];
        int bDepth = depth[b];

        while (aDepth != bDepth) {
            if (aDepth > bDepth) {
                a = parents[a];
                aDepth--;
            } else {
                b = parents[b];
                bDepth--;
            }
        }
        while (a != b) {
            a = parents[a];
            b = parents[b];
        }
        return a;
    }
}