[백준] 3584 가장 가까운 공통 조상

문제 출처: https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

 

1. 입력

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

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

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

: A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

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

 

2. 출력

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

 

3. 풀이

: 테스트 케이스 수를 입력받는다.

: 테스트 케이스 수만큼 반복하면서 노드의 수를 입력받는다.

: 부모 자식관계를 입력받아 부모 배열에 저장한다.

: 공통 조상이 궁금한 정점을 입력받고, 첫번째 정점의 부모를 따라 올라가면서 HashSet에 담는다.

: 두 번째 정점도 부모를 따라 올라가면서 처음 저장한 HashSet에 현재 부모가 존재하는지 확인하고 만약 있다면 반복을 멈추고 해당 부모 번호를 출력한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws Exception{
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 0; tc < T; tc++) {
			int N = Integer.parseInt(br.readLine());
			
			int[] parents = new int[N+1];
			for(int i = 0; i < N-1; i++) {
				st = new StringTokenizer(br.readLine());
				int p = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				
				parents[c] = p;
			}
			
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			HashSet<Integer> hs = new HashSet<>(); 
			while(true) {
				hs.add(v1);
				if(parents[v1] != 0) v1 = parents[v1];
				else break;
			}
			
			while(true) {
				if(hs.remove(v2)) break;
				v2 = parents[v2];
			}
			
			sb.append(v2 + "\n");
		}
		System.out.println(sb);
	}
	
}