[BOJ 백준] LCA 2(11438) Java

링크 : https://www.acmicpc.net/problem/11438

 

문제 설명 : 

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

 

입력 : 

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

 

출력 : 

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

 

예제 입력 : 

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15

 

예제 출력 : 

2
4
2
1
3
1

 

 

접근법 : 

1) 어떻게 풀 것인가?

문제 제목부터 대놓고 LCA (Lowest Common Ancestor)이다. 

즉, 가장 첫번째 공통조상을 구하는 문제이다.

 

예제에 주어진 위 트리를 기준으로 본다면, 

⑪ 과 ④ 의 첫번째 공통조상은 ② 이고, 

⑩ 과 ⑧ 의 첫번째 공통조상은 ① 이고,

⑥ 과 ⑤ 의 첫번째 공통조상은 ② 이다.

 

먼저 2개 정점의 depth (Root로부터 떨어져 있는 거리)를 파악해서 맞춘 후 

위로 올라가서 같아지는 첫번째 공통조상을 찾으면 된다.

 

그런데 N이 10만이고, M도 10만이다.

한 번의 최소공통조상을 찾을때 N번의 연산을 한 다면 10만*10만으로 시간초과가 나게 된다.

즉, 한 번의 최소 공통 조상을 찾을때 logN으로 연산을 해야 O(M log N)으로 풀 수 있는 문제이다.

 

DP를 활용해 LCA를 구현하면 이를 해결할 수 있다.

주요 점화식은 정점 V의 2^K번째 조상 정점을 parent[K][V]라고 할때,

parent[K][V] = parent[K-1][parent[K-1][v]]; 이다.

 

이를 활용하면 아래의 로직으로 풀 수 있다.

자세한 내용은 코드 참고.

1. 모든 정점의 depth를 depth[ i ]에 기록한다.

2. parent[K][V]를 모두 채운다 (아래 코드 fillParent( ) 참고)

3. LCA를 진행한다.

 

 

2) 시간복잡도

쿼리 횟수 M * 1번 연산시 시간 logN = O (M log N) 으로 문제를 통과하는데 무리는 없다.

(Java 기준 -  992ms)

 

3) 공간복잡도

N(10만)개의 Tree 이며, 인접리스트나 간선이 없으므로 고려하지 않음.

 

4) 풀면서 놓쳤던점

없음

 

5) 이 문제를 통해 얻어갈 것

① DFS 활용 (깊이 구하기)

② Tree 만들기

③ LCA 2^N 이용해 구현하기 + DP적 요소 활용

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 11438 LCA 2
public class Main {

	static int N, M, K;

	// LCA 관련 변수
	static int[] depth;    // depth[ i ] 는 i의 깊이
	static int[][] parent; // parent[K][V] 정점 V의 2^K번째 조상 정점 번호
							// parent[K][V] = parent[K-1][parent[K-1][V]];

	// TREE 변수
	static ArrayList[] tree;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		// 1. 입력 & 변수 준비
		N = Integer.parseInt(br.readLine());

		// 2^K >= N인 첫번째 K 찾기,  문제조건 : N >= 2, K를 -1부터 시작해야 아래 값이 나옴
		// N이 17이면 2^4 번째 조상까지 기록 필요    17 = 2^4 + 2^0
		// N이 16이면 2^4 번째 조상까지 기록 필요    16 = 2^4
		// N이 15이면 2^3 번째 조상까지 기록 필요    15 = 2^3 + 2^2 + 2^1 + 2^0
		K = -1;  
		for (int i = 1; i <= N; i *= 2) {
			K++;
		}
		
		// LCA 관련 변수 초기화
		depth = new int[N + 1];
		parent = new int[K + 1][N + 1];          // 2^K 까지 표현해야하므로 K+1로 선언

		// TREE 변수 초기화
		tree = new ArrayList[N+1];
		for (int i = 1; i <= N; i++) {
			tree[i] = new ArrayList<Integer>();
		}

		int a,b;
		for (int i = 1; i <= N-1; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			// 양방향 간선
			tree[a].add(b);
			tree[b].add(a);
		}
		
		// 2. DEPTH 확인
		dfs(1, 1);
		
		// 3. 2^K 까지 parent 채우기
		fillParent();
		
		// 4. LCA 진행
		M = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i=1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			sb.append(lca(a,b)+"\n");
		}

		System.out.println(sb.toString());

		br.close();
	}
	
	// DEPTH 확인, 부모 기록 DFS
	static void dfs(int id, int cnt) {
		// 1. depth를 기록
		depth[id] = cnt;
		
		// 2. 자식들의 depth를 기록
		int len = tree[id].size();
		for (int i = 0; i < len; i++) {
			int next = (Integer)tree[id].get(i);
			
			// 아직 깊이를 모르면 → 미방문 노드
			if (depth[next] == 0) {
				dfs(next, cnt+1);			
				parent[0][next] = id;		// 첫번째 부모를 기록  (2^0)
			}
			
		}
		return;
	}
	
	// 2 ^ K 부모 채우기
	static void fillParent() {
		// 2^K 번째 부모까지 채우기
		for (int i = 1; i<=K; i++) {
			for (int j = 1; j<=N; j++) {
				// parent[K][V] = parent[K-1][parent[K-1][V]];
				parent[i][j] = parent[i-1][parent[i-1][j]];     
			}
		}
	}
	
	// 최소공통조상
	static int lca(int a, int b) {
		// 1. depth[a] >= depth[b] 이도록 조정하기
		if (depth[a] < depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		
		// 2. 더 깊은 a를 2^K승 점프하여 depth를 맞추기
		//    깊이의 차를 2제곱수의 합을 이용해 좁히기 - 큰 수부터 Jump
		for (int i = K; i>=0; i--) {
			if (Math.pow(2, i) <= depth[a] - depth[b]) {
				a = parent[i][a];
			}
		}
		
		// 3. depth를 맞췄는데 같다면 바로 종료
		if (a == b) return a;
		
		// 4. a-b는 같은 depth이므로 2^K승 점프하며 공통부모 바로 아래까지 올리기
		for (int i = K; i >= 0; i--) {
			if (parent[i][a] != parent[i][b]) {
				a = parent[i][a];
				b = parent[i][b];
			}
		}
		
		// 공통부모 바로 아래에서 반복문이 끝났으므로 첫번째 부모 (2^0) 리턴
		return parent[0][a];
	}
}