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

문제

---

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

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

 

 

 

 

풀이

---

최소 공통 조상(Lowest Common Ancestror)을 찾는 문제다.

방식은 여러가지가 있겠지만 HLD(Heavy-Light Decomposition)의 Heavy-Edge 와 Light-Edge 로 구분한 것을 이용해 트리를 분할하여 푸는 방식을 이용하여 풀었다.

 

Heavy-Edge : 각 정점에서 아래로 뻗어나가는 간선중에서 가장 무거운 간선을 의미한다.( 여기서 무겁다는 것은 자식이 가장 많은 정점으로 이어지는 간선을 의미함)

 

Light-Edge : 각 정점에서 아래로 뻗어나가는 간선중 Heavy-Edge 를 제외한 나머지 간선을 의미한다.

 

구하는 방식은 DFS(깊이우선탐색) 알고리즘을 이용하여 구성을 할 수 있다.

 

먼저 각 정점의 무게를 저장을 해놓아야 한다.

static int dfs(int i, int p) {
   	parent[i] = p;
   	size[i] = 1;
   	
   	//HLD 트리를 만들기 위해 노드의 크기를 저장함
   	for(int x : adj[i]) {
   		if(x != p)
  		  	//노드가 가지는 자식의 수를 세서 저장을 함.
			size[i] += dfs(x, i);
  	}
   	
  	return size[i];
}

 

size[] 라는 int 배열을 할당 받아서 각 정점의 번호의 무게를 저장을 했다.

 

HLD 구조를 구성하는 핵심 메소드다.

static void HLD(int i, int p, int cur_chain, int d) {
   	
   	//가장 무거운 체인에서의 깊이를 저장하는 배열.
   	//같은 체인이라면 깊이가 같다
  	depth[i] = d;
   	//체인의 루트위치에 있는 노드의 값을 체인 번호로 가지게 함
   	chain_number[i] = cur_chain;
   	//체인에서 순서를 저장하는 배열
   	chain_index[i] = chain[cur_chain].size();
   	//체인에 노드번호 저장함
   	chain[cur_chain].add(i);
   	
   	int heavy = -1;
   	for(int x : adj[i]) {
   		if(x != p && (heavy == -1 || size[x] > size[heavy])) {
   			heavy = x;
   		}
   	}
   	
   	if(heavy != -1)
   		HLD(heavy, i, cur_chain, d);
   	
   	for(int x : adj[i]) {
   		if(x != p && x != heavy) {
   			HLD(x, i, x, d + 1);
   		}
  	}
}

 

총 4개의 배열을 할당 받아서 사용하였는데,

depth[] : 깊이를 저장하는 배열이다. 가장 무거운 체인에 있으면 깊이가 0 이다. 무거운 체인을 기준으로 깊어 질 수록 숫자가 커진다. 같은 체인안에 속해있는 정점들의 깊이는 모두 같다.

 

chain_number[] : 몇번 체인에 속하는지 저장하는 배열이다. 나중에 조상을 찾을 때 같은 체인에 속해있으면 같은 조상을 가지고 있으므로 반복문을 끝내는 조건으로 사용한다.

 

chain_index[] : 체인에서의 위치를 저장하는 배열이다. 숫자가 작을 수록 조상이다.

 

chain[] : 리스트로 구성하였고, 각각의 chain 에 포함한 정점의 번호를 저장한다.

 

구동방식은 하나씩 읽어보면서 이해하면 빠를 것같다. 

핵심은 노드에어 이어지는 정점을 돌면서 Heavy-Edge로 이어지는 정점인지 Light-Edge 로 연결되어지는 정점인지에 따라 저장되는 chain 이 나뉜다.

 

위에서 구성한 배열들을 이용하여 공통조상을 가리는 코드다.

static int LCA(int a, int b) {
    	
   	//체인의 번호가 같아 질 때까지 반복문을 수행함
  	while(chain_number[a] != chain_number[b]) {
   		if(depth[a] > depth[b]) {
   			a = parent[chain_number[a]];
   		}
   		else {
  			b = parent[chain_number[b]];
   		}
   	}
   	
   	return chain_index[a] > chain_index[b] ? b : a;
}

2가지 경우가 존재한다.

1. 체인의 번호가 같은 경우

2. 다른 체인에 속해있는 경우

 

1번의 경우는 쉽다. 체인의 번호가 같다면 chain_index 가 더 작은 정점을 찾으면 된다.

2번의 경우가 좀 복잡한데, 이때는 체인의 번호가 같아질 때까지 깊이 배열을 이용하여 반복문을 수행한다.

깊이가 같아도 체인의 번호가 다를 수 있기 때문에 이럴 때는 오른쪽 왼쪽 노드중 임의의 노드를 이동시키면 된다.

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.Pattern;


public class Main {

	static StringBuilder sb = new StringBuilder();
	static int[] size = new int[100005];
	static int[] parent = new int[100005];
	static List<Integer>[] adj = new List[100005];
	
	static List<Integer>[] chain = new List[100005];
	static int[] depth = new int[100005];
	static int[] chain_number = new int[100005];
	static int[] chain_index = new int[100005];
	

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        for(int i = 0 ; i < 100005 ; i++) {
    		adj[i] = new LinkedList<Integer>();
    		chain[i] = new LinkedList<Integer>();
    	}
        
        
        int n = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer st = null;
        for(int i = 0 ; i < n - 1; i++) {
        	st = new StringTokenizer(bufferedReader.readLine());
        	
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());        	
        	
        	adj[a].add(b);
        	adj[b].add(a);
        }
        
        dfs(1, 0);
        HLD(1, 0, 1, 0);
        
        int m = Integer.parseInt(bufferedReader.readLine());
        
        for(int i = 0 ; i < m ; i++) {
        	st = new StringTokenizer(bufferedReader.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	sb.append(LCA(a, b)).append("\n");
        }
        System.out.println(sb);
    }
    
    static int dfs(int i, int p) {
    	parent[i] = p;
    	size[i] = 1;
    	
    	//HLD 트리를 만들기 위해 노드의 크기를 저장함
    	for(int x : adj[i]) {
    		if(x != p)
    			//노드가 가지는 자식의 수를 세서 저장을 함.
    			size[i] += dfs(x, i);
    	}
    	
    	return size[i];
    }
    
    static void HLD(int i, int p, int cur_chain, int d) {
    	
    	//가장 무거운 체인에서의 깊이를 저장하는 배열.
    	//같은 체인이라면 깊이가 같다
    	depth[i] = d;
    	//체인의 루트위치에 있는 노드의 값을 체인 번호로 가지게 함
    	chain_number[i] = cur_chain;
    	//체인에서 순서를 저장하는 배열
    	chain_index[i] = chain[cur_chain].size();
    	//체인에 노드번호 저장함
    	chain[cur_chain].add(i);
    	
    	int heavy = -1;
    	for(int x : adj[i]) {
    		if(x != p && (heavy == -1 || size[x] > size[heavy])) {
    			heavy = x;
    		}
    	}
    	
    	if(heavy != -1)
    		HLD(heavy, i, cur_chain, d);
    	
    	for(int x : adj[i]) {
    		if(x != p && x != heavy) {
    			HLD(x, i, x, d + 1);
    		}
    	}
    }
    
    static int LCA(int a, int b) {
    	
    	//체인의 번호가 같아 질 때까지 반복문을 수행함
    	while(chain_number[a] != chain_number[b]) {
    		if(depth[a] > depth[b]) {
    			a = parent[chain_number[a]];
    		}
    		else {
    			b = parent[chain_number[b]];
    		}
    	}
    	
    	return chain_index[a] > chain_index[b] ? b : a;
    }
    
}

 

 

이 외에 Sparse Table 을 이용한 DP 풀이도 있다.

conpulake.tistory.com/61

백준 11438 ( LCA 2) - DP 풀이