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

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

난이도: 골드4

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

문제

입력

출력

---

[아이디어]

노드마다 부모는 단 하나만 존재한다. 그래서 노드의 부모를 저장해주는 배열을 따로 만들어주었다.

parent[i] = j  => i 의 부모가 j 이다.

 

그 다음 두 노드 중 하나의 노드부터 시작하여 루트까지 방문을 체크해준다. 그 후 나머지 노드에 대해 루트까지 올라가면서 방문한 노드를 만나면 그게 가장 가까운 공통 노드가 된다!

---

[JAVA 코드]

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int T, N;
	static int [] parent;

	public static void main(String[] args) throws NumberFormatException, IOException {
		T = Integer.parseInt(br.readLine());
		for(int t = 0; t < T; t++) {
			N = Integer.parseInt(br.readLine());
			
			parent = new int [N + 1];
			// 부모 초기화
			for(int i = 0; i <= N; i++) {
				parent[i] = i;
			}
			
			// 부모 설정해주기
			for(int i = 0; i < N - 1; i++) {
				tokens = new StringTokenizer(br.readLine());
				int A = Integer.parseInt(tokens.nextToken());
				int B = Integer.parseInt(tokens.nextToken());
				parent[B] = A; // B의 부모가 A
			}
			
			tokens = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(tokens.nextToken());
			int v = Integer.parseInt(tokens.nextToken());
			
			boolean [] visited = new boolean [N + 1];

			// u부터 루트까지 모든 노드를 방문체크 해주기
			visited[u] = true;
			while(u != parent[u]) { // 루트까지 올라가기
				u = parent[u];
				visited[u] = true;
			}
			
			while(true) {
				if(visited[v]) {
					output.append(v + "\n");
					break;
				}
				
				v = parent[v];
			}
		}
		
		System.out.println(output);
	}

}