[백준] 3584 - 가장 가까운 공통 조상 (java)

Baekjoon 3584- 가장 가까운 공통 조상 (클릭 시 이동)

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	4081	2130	1599	53.658%

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

풀이

1. N개의 노드가 있고 각 노드는 하나의 부모를 가진다. 루트노드는 0을 부모로 가지게 했다.
2. N+1개짜리 int형 배열을 만든 후 자식을 index로 값은 부모로 저장한다.
3. 공통조상을 구할 두 노드를 각각 다른 stack에 넣는다.
4. 각 부모를 타고 올라가며 0이 나올 때 까지 stack에 넣는다
5. 각각 stack에서 하나씩 꺼내보며 두개가 다를때까지 비교해본다.
6. 마지막으로 같았던 값이 최소 공통 조상이 된다.

최종 소스코드

package BJ_Practice;

import java.io.*;
import java.util.*;

public class BJ_G4_3584_가장_가까운_공통_조상 {

    static int T, N;
    static int parent[];
    static StringTokenizer st;

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

        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());

            parent = new int[N + 1];

            for (int i = 1; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());

                parent[end] = start;
            }
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            Stack<Integer> firstList = new Stack<>();
            Stack<Integer> secondList = new Stack<>();

            firstList.push(num1);
            secondList.push(num2);

            // 자식부터 최상위 부모(root)까지 탐색
            while (parent[num1] != 0) {
                firstList.push(parent[num1]);
                num1 = parent[num1];
            }
            while (parent[num2] != 0) {
                secondList.push(parent[num2]);
                num2 = parent[num2];
            }

            int first = 0;
            int second = 0;
            int answer = 0;

            // 공통 조상 찾기. 스택에서 꺼냈을 때 같으면 공통 조상이다.
            // 마지막에 같았던 값은 최소 공통 조상이다.
            while (true) {
                if (firstList.isEmpty() || secondList.isEmpty()) {
                    break;
                }
                first = firstList.pop();
                second = secondList.pop();
                if (first != second) {
                    break;
                }
                answer = first;
            }
            System.out.println(answer);
        }
    }
}