[BOJ 11438] LCA 2(최소 공통 조상, 희소 행렬, 시간복잡도, JAVA)

www.acmicpc.net/problem/11438

11438번: LCA 2

 

## 최소 공통 조상

---

최소 공통 조상이란, 트리에 각 노드에서 공통된 조상을 갖을 때 가장 가까이 있는 노드를 의미한다. 만약에, 트리의 높이가 H라고 했을 때, 순차적으로 탐색을 한다면 O(H)만큼 걸릴 것이다. 문제의 조건에서 발생할 수 있는 H는 최대 N과 같으므로, 시간복잡도가 O(N * N)이 되므로 제한 시간안에 정답을 찾을 수 없다.

 

 

 

 

## 희소 행렬

---

위에서 높이를 O(H)에 순차적으로 접근하는 것이 아니라, O(logH)로 접근할 수 있는 방법이 있다. 내가 지금부터 설명하는 개념이 희소 행렬에 정확한 정의인지는 모르겠다. 구글링을 해봐도 희소 행렬에 대해서 정확하게 언급되어 있지 않아서, 문제를 풀면서 느낀 정의를 공유하고자 한다.

 

 

 

각 노드가 가지고 있는 부모 노드에 대한 정보는 순차적인 정보가 아니라, 2의 배수 승이다. 즉, 1번째 정보는 2^0이고, 2번째 정보는 2^1이고, 3번째 정보는 2^2승 ... N번째 정보는 2^(N - 1)이 된다.

 

 

 

각 노드들이 모두 동일하게 위의 정보를 갖고 있을 때, 모든 부모노드들을 방문할 수 있을까에 대한 의문이 당연히 있어야 한다.

 

 

 

우리가 알고 있는 사실, 모든 수는 이진수로 표현할 수 있다. 각 노드들이 가지고 있는 2^N의 정보는 이진 수의 각 수를 의미할 수 있다. 따라서, 노드들이 가진 2^N의 정보로 모든 노드들을 접근할 수 있다.

 

 

 

 

## 해설코드(Java)

---

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static ArrayList<Integer>[] alist;
    static int[] depth;
    static int[][] ac;
    
    static int getPow(int num, int x){
        int result = 1;
        
        for(int i = 1; i <= x; i++)
            result *= num;
            
        return result;
    }
    
    static void getTree(int here, int parent){
        int cur = here;
        depth[cur] = depth[parent] + 1;
        
        ac[here][0] = parent;
        for(int i = 1; i <= 20; i++)
            ac[here][i] = ac[ac[here][i - 1]][i - 1];
        
        for(int i = 0; i < alist[here].size(); i++){
            if(parent != alist[here].get(i))
                getTree(alist[here].get(i), here);
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        N = Integer.valueOf(br.readLine());
        
        alist = new ArrayList[N + 1];
        for(int i = 0; i < alist.length; i++)
            alist[i] = new ArrayList<>();    
            
        depth = new int[N + 1];
        ac = new int[N + 1][21];
        
        for(int i = 0; i < N - 1; i++){
            String[] sArr = br.readLine().split(" ");
            int n1 = Integer.valueOf(sArr[0]);
            int n2 = Integer.valueOf(sArr[1]);
            
            alist[n1].add(n2);
            alist[n2].add(n1);
            
            
        }
        
        depth[1] = 0;
        getTree(1, 0);
        
        M = Integer.valueOf(br.readLine());
        for(int i = 0; i < M; i++){
            String[] sArr = br.readLine().split(" ");
            int n1 = Integer.valueOf(sArr[0]);
            int n2 = Integer.valueOf(sArr[1]);
            
            if(depth[n1] > depth[n2]){
                int temp = n1;
                n1 = n2;
                n2 = temp;
            }
            
            
            for(int j = 20; j >= 0; j--){
                if(depth[ac[n2][j]] >= depth[n1])
                    n2 = ac[n2][j];
            }
            
            int lca = n1;
            
            if(n1 != n2){
                for(int j = 20; j >= 0; j--){
                    if(ac[n2][j] != ac[n1][j]){
                        n2 = ac[n2][j];
                        n1 = ac[n1][j];
                    }else
                        lca = ac[n2][j];
                }
            }
            
            bw.write(lca + "\n");
        }
        bw.flush();
    }
}