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

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

문제

루트가 있는 트리(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 이하의 정수로 이름 붙여집니다. 테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

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

풀이

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

최종 소스코드

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 firstList = new Stack<>(); Stack 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); } } }

from http://skdltm117.tistory.com/51 by ccl(A) rewrite - 2021-12-25 18:26:54