[알고리즘] 최소 공통 조상

1. 개념

트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상이라고 한다.

 

2. 원리

1) 일반적인 최소 공통 조상 구하기

• 4번과 15번 노드의 최소 공통 조상을 구한다고 가정. 
• 루트 노드에서 탐색을 시작해 4번의 부모 노드와 깊이를 저장, 루트 노드에서 탐색을 시작해 15번의 부모 노드와 깊이를 저장
• 선택된 두 노드의 깊이가 같은 경우 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복 - 1
• 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 올려서 같은 깊이로 맞추기 그리고 1을 진행

트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있다는 단점이 있다.

 

2) 최소 공통 조상 빠르게 구하기

① 2의 k제곱번째 위치의 부모 노드 배열

정의

서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려 주는 방식에서 2의 k제곱씩 올라가 비교한다. 따라서 2의 k제곱번째 위치의 부모 노드를 저장해둬야 한다.

P[K][N] = N번 노드의 2의 k번째 부모의 노드 번호

 

점화식

P[K][N] = P[K-1][P[K-1][N]]

• N번 노드의 2의 k번째 부모의 노드 번호는 N번 노드의 2의 k-1번째 부모의 노드 번호의 2의 k-1번째 부모 노드이다.
• K는 트리의 깊이 > 2의 k제곱을 만족하는 최댓값

예시

위 상황에서 트리의 깊이는 5이기 때문에 k의 최댓값은 2이다.

따라서 부모 노드 배열을 완성하면 다음과 같다. k가 0인 것은 바로 자신의 부모를 의미하는 것이고, k가 1인 것은 2번째 부모, k가 2인 것은 3번째 부모를 의미하는 것이다.

 

② 선택된 두 노드의 깊이 맞추기

• 노드 2개를 선택해서 조상을 찾는다고 하자.
• 선택된 두 노드의 깊이가 다르다면 깊이를 맞추기 위해 더 깊이 있는 노드의 2의 k제곱번째 부모를 찾는다. -1
• 1을 높이가 같아질 때까지 반복한다.

③ 최소 공통 조상 찾기

• 높이가 같아졌을 때 2의 k제곱번째 부모를 찾아가며 같은 노드가 될 때까지 반복한다.
• k가 2일 때 같아졌다고 하면 위 결과의 의미는 두 노드의 공통 조상이 2의 1제곱에서 2의 2제곱 사이에 존재한다는 뜻이다.
• 따라서 k가 1일 때로, 즉 두 노드의 공통 조상이 2의 1제곱인 곳으로 가본다. 2의 1제곱에서 값이 존재할 수도 있고 2의 2제곱에서 값이 존재할 수도 있으니 다시 시작해보는 것이다.
• 위에서 다시 시작해서 k가 0 일때 실행해보고 같은 값이 나오면 그 값이 최소 공통 조상이다.
• 만약 k가 0일 때 안 나오면 k가 1일 때 실행해보면 되고 그 값이 최소 공통 조상이 된다.

 

3. 구현

1) 일반적인 최소 공통 조상 구하기

public static int LCA(int a, int b){
    if(depth[a] < depth[b]){ // 깊이가 깊은 것을 a로, 깊이가 낮은 것을 b로 설정
        int temp = a;
        a = b;
        b = temp;
    }
    while(depth[a] != depth[b]){ // 둘 깊이 같아질 때까지 깊이 깊은 것을 부모로 올린다
        a = parent[a];
    }

    while(a!=b){ // 둘 조상 같아질 때까지 각자를 부모로 올린다
        a = parent[a];
        b = parent[b];
    }

    return a;
}

public static void BFS(int num){
    Queue<Integer> q = new LinkedList<>();
    q.add(num);
    visited[num] = true;
    int level = 1;
    int nowSize = 1;
    int count = 0;

    while(!q.isEmpty()){
        int now = q.poll();
        for(int next : adjList[now]){
            if(!visited[next]){
                visited[next] = true;
                q.add(next);
                parent[next] = now;
                depth[next] = level;
            }
        }
        count++;
        if(count == nowSize){ // 이번 높이에 해당하는 모든 노드를 방문했을 때
            count = 0;
            nowSize = q.size();
            level++;
        }
    }

}

2) 최소 공통 조상 빠르게 구하기

 

 

4. 관련 문제

백준 11437

GitHub - Lee-Min-Jung/coding_test_practice

백준 11438

GitHub - Lee-Min-Jung/coding_test_practice