[백준]#11437 LCA

문제

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(가장 가까운 공통 조상 찾기) 문제로 해당 알고리즘이 어떻게 구현되는지 알고 있다면 쉽게 풀 수 있다.

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] parent;
    static int[] depth;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        depth = new int[N+1];
        parent = new int[N+1];
        graph = new ArrayList[N+1];

        for(int i=1; i<=N; i++)
            graph[i] = new ArrayList<>();

        for(int i=0; i<N-1; i++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);

            graph[start].add(end);
            graph[end].add(start);
        }

        bfs();

        int M = Integer.parseInt(br.readLine());
        for(int i=0; i<M; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

            sb.append(lca(a, b)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static int lca(int a, int b) {

        while(true) {
            if(a==b)
                return a;

            if(depth[a]==depth[b]) {
                while(a!=b) {
                    a = parent[a];
                    b = parent[b];
                }
            }

            else {
                if(depth[a]>depth[b]) {
                    while(depth[a]>depth[b]) {
                        a = parent[a];
                    }
                }

                else {
                    while(depth[a]<depth[b]) {
                        b = parent[b];
                    }
                }
            }
        }
    }

    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        parent[1] = 1;

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (int i=0; i<graph[cur].size(); i++) {
                int next = graph[cur].get(i);

                if(parent[next]!=0)
                    continue;

                depth[next] = depth[cur] + 1;
                parent[next] = cur;
                queue.add(next);
            }
        }
    }
}