[백준] 가장 가까운 공통 조상 - 골드4, 트리(Tree)

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

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

 

이 문제의 분류를 LCA(Lowest Common Ancestor) 알고리즘 분류라고 할 수 있습니다.

이 문제를 풀 수 있는 다른 알고리즘이 존재하는 것같지만, 

가장 간단하게 풀 수 있는 방법으로 구현했습니다.

 

부모노드에서부터 자식노드로 가는 간선 대신에

자식노드에서 부모노드로 가는 간선을 구현한뒤, 방문처리를 하면서 루트노드까지 올라갑니다.

 

[step 1] 목표 자식노드에서부터 하나씩 올라가면서 만나는 노드마다 방문처리를 해줍니다. 

이떄, 본인이 LCA가 될 수 있으므로 본인 노드도 시작할떄 방문처리를 해주어야합니다.

[step 2] 두번째 자식노드는 노드를 하나씩 올라가면서 방문한적이 있는 노드라면 LCA이므로 노드를 만날시 return 하고 해당 노드 번호를 출력하면 됩니다.

 

 

 

 

코드입니다.

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>();
	static int answer=0;
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		
		while(T > 0) {
			answer=0;
			int N = sc.nextInt();
			tree = new ArrayList<ArrayList<Integer>>();
			for(int i=0;i<=N;i++) {
				tree.add(new ArrayList<Integer>());
			}
			visited = new boolean[N+1];
			for(int i=0;i<N-1;i++) {
				int s = sc.nextInt();
				int e = sc.nextInt();
//				tree.get(s).add(e);
				tree.get(e).add(s);
			}
			int targetnode1 = sc.nextInt();
			int targetnode2 = sc.nextInt();
			firstchildtoRoot(targetnode1);
			
			secondchildtoRoot(targetnode2);
			System.out.println(answer);
			T-=1;
		}
	}
	
	static void firstchildtoRoot(int start) {
		visited[start] = true;
		for(int i=0;i<tree.get(start).size();i++) {
			if(visited[tree.get(start).get(i)] == false) {
				firstchildtoRoot(tree.get(start).get(i));
			}
		}
	}
	
	static void secondchildtoRoot(int start) {
		if(visited[start] == true) {
			answer = start;
			return ;
		}
		for(int i=0;i<tree.get(start).size();i++) {
			secondchildtoRoot(tree.get(start).get(i));
		}		
	}
}