백준 11438 ( LCA 2) - DP 풀이

문제

---

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

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

 

 

풀이

---

conpulake.tistory.com/60

백준 11438 (LCA 2) - 최소공통조상(HLD 풀이)

 

위의 링크에서 HLD 풀이를 했다.

좀 더 직관적이고 보편적인 풀이인 DP(Dynamic Programming) 을 이용한 풀이를 올려보려 한다.

다른말로 sparse table을 사용한 풀이다. 

 

 

해당 정점의 조상을 순서별로 저장을 해놓고 찾는 방식이라고 생각하면 된다.

 

1. DFS 탐색을 통해 각 노드별 깊이(depth)를 구해 배열에 저장을 한다. 이 때의 첫번째 조상을 parents배열에 저장해 준다.
2. DP 알고리즘을 통해 각 노드의 2^i 번째 조상노드를 구해 parents 배열에 저장한다.
3. 주어진 a 와 b 의 깊이를 맞춘 후, 차례로 2^i번 째 조상노드를 구해가며 최소 공통 조상을 찾는다.

위의 순서에 맞게 풀면 된다.

 

DP 알고리즘이라는 것이 어려웠다.

2^i 번째 조상노드를 저장한다는 개념이 이해를 돕기위해 코드를 보며 설명하겠다.

for(int i = 1; i < k ; i++) {
    	for(int j = 1; j <= n ; j++) {
    		parents[j][i] = parents[parents[j][i - 1]][i - 1];
    	}
}

앞서 DFS 를 통해 바로위의 조상을 parents[i][0]에 저장을 해두었다.

그럼 i 노드의 2^1 번째 조상은 parents[i][1] 부분에 저장이 되는데 이는 

i 노드의 2^0 번째 조상의 2^0 번째 조상이 된다. 

이를 식으로 정리하면 parents[i][1] = parents[parents[i][0][0] 이 되는 것이다.

이렇게 최대 깊이 K 까지 반복문을 통해 미리 모든 조상을 DP에 저장을 해두고 문제를 풀면된다.

 

 

<전체코드>

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


public class Main {

	static StringBuilder sb = new StringBuilder();
	static int[] depth;
	static int[][] parents;
	static List<Integer>[] tree;
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(bufferedReader.readLine());
        
        tree = new List[n + 1];
        
        for(int i = 0 ; i <= n ; i++) {
        	tree[i] = new LinkedList<Integer>();
        }
        
        for(int i = 0 ; i < n - 1; i++) {
        	StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        	
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	tree[a].add(b);
        	tree[b].add(a);
        }
        
        int tmp = 1;
        int K = 0;
        while(tmp <= n) {
        	tmp <<= 1;
        	K++;
        }
        
        depth = new int[n + 1];
        parents = new int[n + 1][K];
        
        DFS(1, 1);
        DP_Algorithm(K, n);
        
        int m = Integer.parseInt(bufferedReader.readLine());
        
        for(int i = 0 ; i < m ; i++) {
        	StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        	
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	sb.append(LCA(a, b, K) + "\n");
        }
        
        System.out.println(sb);
    }
    
    public static void DFS(int node, int cnt) {
    	depth[node] = cnt;
    	
    	for(int next : tree[node]) {
    		if(depth[next] == 0) {
    			DFS(next, cnt + 1);
    			parents[next][0] = node;
    		}
    	}
    }
    
    public static void DP_Algorithm(int k, int n) {
    	for(int i = 1; i < k ; i++) {
    		for(int j = 1; j <= n ; j++) {
    			parents[j][i] = parents[parents[j][i - 1]][i - 1];
    		}
    	}
    }
    
    public static int LCA(int a, int b, int k) {
    	if(depth[a] < depth[b]) {
    		int temp = a;
    		a = b;
    		b = temp;
    	}
    	
    	for(int i = k - 1 ; i >= 0 ; i--) {
    		if(Math.pow(2, i) <= depth[a] - depth[b]) {
    			a = parents[a][i];
    		}
    	}
    	
    	if(a == b)
    		return a;
    	
    	for(int i = k - 1 ; i >= 0 ; i--) {
    		if(parents[a][i] != parents[b][i]) {
    			a = parents[a][i];
    			b = parents[b][i];
    		}
    	}
    	
    	return parents[a][0];
    }
}

 

 

전체적인 코드를 이해하고 푸는것은 Sparse Table 을 이용한 방식이 쉽지만, HLD를 이용한 방식이 시간복잡도가 짧고 고차원 적인 방법이므로 익혀두길 바란다.