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

#3584 가장 가까운 공통 조상

난이도 : 골드 4

유형 : 트리 / 최소 공통 조상(LCA)

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

▸ 문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

▸ 입력

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

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

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

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

▸ 출력

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

 

문제 풀이  

해당 문제는 최대 노드의 수가 1만개로 일반적인 LCA 풀이 방법으로 풀이가 가능하다. 데이터 크기가 주어질 경우 DP 혹은 세그먼트 트리를 통해 풀이를 해줘야한다.

 

3,5번 노드의 LCA는 3번 노드

설계 

1. 노드 연결 데이터를 입력 받아 저장한다.
   1. 루트노드를 선별하는 방식은 자식 노드는 check를 해준다. 그리고 입력이 끝난 후에 check가 되지 않은 노드가 루트노드이다.
2. 저장된 노드 데이터를 root노드부터 DFS 탐색하여 노드의 부모 노드와 높이의 값을 저장한다. depth[], parents[]
3. 두 a,b 노드의 최소 공통 조상을 구해준다.
   1. 두 노드의 높이(depth)를 맞춰준다.  ah--; or bh--;
   2. 높이가 일치되었으면 부모노드가 일치할 때 까지 부모노드를 탐색한 후 일치하게 되면 출력한다. while(a!=b) a = parents[a]; b = parents[b];

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main{

	static List<Integer>[] list;
	static int[] parent, depth;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		for(int t=0; t<tc; t++) {
			int n = Integer.parseInt(br.readLine());
			
			parent = new int[n+1];
			depth = new int[n+1];
			list = new ArrayList[n+1];
			for(int i=1; i<n+1; i++) {
				list[i] = new ArrayList<>();
			}
			
			boolean[] rootCheck = new boolean[n+1];
			Arrays.fill(rootCheck, true);
			StringTokenizer st;
			for(int i=0; i<n-1; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				list[a].add(b);
				rootCheck[b] = false;
			}
			int rootIdx=0;
			for(int i=1; i<n+1; i++) {
				if(rootCheck[i]) {
					rootIdx =i; 
					break;
				}
			}
			
			init(rootIdx,1,0);
			
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			System.out.println(LCA(a,b));
		}
		
	}

	static void init(int cur, int h, int pa) {
		depth[cur] = h;
		parent[cur] = pa;
		for(int nxt : list[cur]) {
			if(nxt != pa) {
				init(nxt, h+1, cur);
			}
		}
	}
	
	static int LCA(int a, int b) {
		int ah = depth[a];
		int bh = depth[b];
		while(ah > bh) {
			a = parent[a];
			ah--;
		}
		
		while(bh > ah) {
			b = parent[b];
			bh--;
		}
		
		while(a!=b) {
			a = parent[a];
			b = parent[b];
		}
		
		return a;
	}
}