[개념] 최소 공통 조상 (LCA, Lowest Common Ancestor)

# 최소 공통 조상 (LCA)

• 정점 A와 정점 B가 각각 자신을 포함하여 초상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 구하기
• 처음 아이디어 = 정점의 부모를 따라 1칸씩 올라가자
  • 시간 복잡도 = O(N)  =>  어떻게 더 빠르게 찾을 수 있을까?
  • 1칸씩 올라가는 것이 아닌 2^K씩 올라가자 => 시간 복잡도 = O(logN)
    
    • 이때 다른 수도 아닌 2^K인 이유는??? 모든 수는 이진수로 나타낼 수 있기 때문에
• parent[0][V] = 정점 V의 1(=2^0)번째 부모
  parent[1][V] = 정점 V의 2(=2^1)번째 부모
                   ★ = 정점 V의 1번째 부모의 1번째 부모 ★
  => parent[1][V] = parent[0][ parent[0][V] ]
  ★★ parent[K][V] = parent[K-1][ parent[K-1][V] ] ★★

---

# 코드

1. 트리의 최대 높이 구하기(K)

public static int getHeight(){
	return (int) Math.ceil(Math.log(N) / Math.log(2)) + 1;
}

 

2. DFS - depth 확인, 첫 번째 부모(parent[0][V]) 기록

• int[] depth = new int[정점 개수 + 1];
• int[][] parent = new int[K+1][정점 개수 + 1];
  • parent[K][V] = 정점V의 2^K번째 조상 정점 번호
• dfs(1,1);

public static void dfs(int id, int cnt){
    depth[id] = cnt; // 정점 id의 depth = cnt;
    
    // 자식들의 depth 구하기
    int len = tree[id].size(); // 자식 개수
    for(int i=0;i<len;i++){
        int next = tree[id].get(i);
        
        if(depth[next] == 0){ // 깊이 갱신 안 된 자식인 경우
            dfs(next, cnt+1);
            parent[0][next] = id; // 1(=2^0)번째 부모 기록
        }
    }
}

 

3. 2^K번째 부모까지 기록하기

public static void getParent(){
    for(int i=1;i<=K;i++){
        for(int j=1;j<=N;j++){
            parent[i][j] = parent[i-1][parent[i-1][j]];
        }
    }
}

 

4. 정점 a와 정점 b의 최소 공통 조상 구하기

public static int lca(int a, int b){
    // 정점 a와 정점 b 중 depth가 더 큰 정점을 a, 더 작은 정점을 b로 변경
    // => depth[a] >= depth[b]가 되도록 변경
    if(depth[a] < depth[b]){
        int temp = a;
        a = b;
        b = temp;
    }
    
    // a에서부터 2^K만큼 올라가서 b와 depth 맞추기
    for(int i=K;i>=0;i--){
        if(Math.pow(2,i) <= depth[a] - depth[b])
            a = parent[i][a]; // 정점 a의 2^i번째 조상으로 변경
    }
    
    // depth를 같도록 했을 때, 두 정점이 같은 정점인 경우 => return a
    if(a == b) {
        return a;
    }
    
    // 공통 조상 바로 아래까지 2^K만큼 점프하기
    for(int i=K;i>=0;i--){
        if(parent[i][a] != parent[i][b]){
            a = parent[i][a];
            b = parent[i][b];
        }
    }
    
    // 공통 조상 return
    return parent[0][a];
}