🔗 Problem

https://www.acmicpc.net/problem/3584

👩‍💻 Code

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

// 가장 가까운 공통 조상

public class BJ3584 {

	static int numT;
	static int numN;
	static int[] parent;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		numT = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int i = 0; i < numT; i++) {
			numN = Integer.parseInt(br.readLine());
			parent = new int[numN + 1];
			visited = new boolean[numN + 1];
			for(int j = 1; j <= numN; j++) {
				parent[j] = j;
			}
			
			for(int k = 0; k < numN - 1; k++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
			
				parent[b] = a;
			}
			
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
		
			setParents(a);
			sb.append(findCommon(b)).append('\n');
		}
		
		System.out.println(sb.toString());
	}
	
	private static int setParents(int x) {
		
		visited[x] = true;		// x의 부모들은 true로 설정
		
		if(parent[x] == x) return x;
		return setParents(parent[x]);
	}
	
	private static int findCommon(int b) {
		
		if(parent[b] == b) return b;
		else {
			if(visited[b]) return b;		// visited[b]가 true라면 가장 가까운 공통 부모이다.
			return findCommon(parent[b]);
		}
	}
}

📌 Note

아이디어

• Union Find 문제라고 생각하고 풀었는데, LCA(Lowest Common Ancestor)라는 알고리즘이 따로 있었다.
• 위 풀이는 Union Find 바탕으로, (내가 생각했을 때)
  두 노드 a와 b의 가장 가까운 공통 조상을 찾는다고 하였을 때
  setParents(int a)를 통해 a의 부모들에 대해 parents[a] = true 로 설정하고
  findCommon(int b)를 통해 b의 부모들을 찾아가는 과정에서, parents[b] == true라면 a와 공통 조상이므로 해당 노드를 반환하는 방법으로 구현하였다.