G3584. 가장 가까운 공통 조상

문제

제출 코드

• 사용 알고리즘 : DFS

각 노드들의 부모를 저장하고, 탐색할 두 노드의 부모들을 DFS를 통해 가까운 순서대로 스택에 담아준다.

이후 위에서부터 동시에 하나씩 꺼내어보면서, 마지막으로 동일했던 노드를 출력하면 된다.

package gold;

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

public class G3584_nearestCommonAncestor {
	static int[] parents;

	static void findParents(int child, Stack<Integer> stack) {
		stack.add(child);

		if(parents[child] != 0) {
			findParents(parents[child], stack);
		}

	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int t=0; t<T; t++) {
			int N = Integer.parseInt(br.readLine());
			parents = new int[N+1];

			for(int i=0; i<N-1; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int parent = Integer.parseInt(st.nextToken());
				int child = Integer.parseInt(st.nextToken());
				parents[child] = parent;
			}

			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			Stack<Integer> stack_a = new Stack<Integer>();
			Stack<Integer> stack_b = new Stack<Integer>();

			findParents(a, stack_a);
			findParents(b, stack_b);

			int result = -1;
			while(!stack_a.isEmpty() && !stack_b.isEmpty()){
				int parent_a = stack_a.pop();
				int parent_b = stack_b.pop();

				if(parent_a == parent_b) {
					result = parent_a;
				}else {
					break;
				}
			}

			System.out.println(result);
		}
	}

}