[백준 #11437] LCA - JAVA(자바)

문제

https://www.acmicpc.net/problem/11437

 

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

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

해설

두 노드의 공통 조상을 찾는 문제이다. 먼저 찾고자하는 두 노드가 있을 때 두 노드를 같은 높이의 노드로 이동한다. 그리고 같은 높이가 되면 두 노드가 같은 노드가 될 때 까지 루트 노드 방향으로 찾으면 된다. 이 과정을 한 칸씩 오르게 되면 최악일 경우 O(n)이 되고 전체 시간 복잡도는 O(n*m) 이 된다. 따라서 효율성을 고려하기 위해서는 dp 나 세그먼트 트리 방식을 사용해야 한다고 한다.

코드

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

public class Main {

    public static ArrayList<Integer>[] graph;
    public static int[] p; // parent
    public static int[] d; // depth
    public static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            String[] split = br.readLine().split(" ");
            int a = Integer.parseInt(split[0]);
            int b = Integer.parseInt(split[1]);
            graph[a].add(b);
            graph[b].add(a);
        }

        p = new int[n + 1];
        d = new int[n + 1];
        visited = new boolean[n + 1];

        // 1. 각 노드의 깊이를 구하기
        dfs(1, 0);


        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            String[] split = br.readLine().split(" ");
            int a = Integer.parseInt(split[0]);
            int b = Integer.parseInt(split[1]);
            sb.append(lca(a, b)).append("\n");
        }
        System.out.print(sb);
    }

    public static void dfs(int node, int depth){
        visited[node] = true;
        d[node] = depth;

        for(Integer next : graph[node]){
            if(visited[next]) continue;
            p[next] = node;
            dfs(next, depth + 1);
        }
    }

    // least common ancestor
    // 시간복잡도 O(n*m)
    public static int lca(int a, int b){
        // 먼저 깊이가 같은 노드로 이동
        while(d[a] != d[b]){
            if(d[a] < d[b]){
                b = p[b];
            }else{
                a = p[a];
            }
        }
        while(a != b){
            a = p[a];
            b = p[b];
        }
        return a;
    }
}