[백준]#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

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

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

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int t=0; t<T; t++) {
            N = Integer.parseInt(br.readLine());
            depth = new int[N+1];
            parent = new int[N+1];
            int[] cnt = new int[N+1];
            tree = new ArrayList[N+1];
            for(int i=1; i<=N; i++)
                tree[i] = new ArrayList<>();

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

                tree[a].add(b);
                cnt[b]++;         //부모 있는 지 체크
            }

            int root = 0;
            for(int i=1; i<=N; i++) {
                if(cnt[i]==0) {
                    root = i;     //부모가 없는 노드가 루트
                    break;
                }
            }

            make_tree(root);      //루트부터 트리 만들기

            input = br.readLine().split(" ");

            System.out.println(lca(Integer.parseInt(input[0]), Integer.parseInt(input[1])));
        }
    }

    public 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]) {
                    b = parent[b];
                }
            }

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

    public static void make_tree(int root) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);

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

            for(int child : tree[temp]) {
                if(parent[child]!=0) continue;

                parent[child] = temp;
                depth[child] = depth[temp]+1;   //부모로부터 깊이 1씩 증가
                queue.add(child);
            }
        }
    }
}