최소 공통 조상 구하기(LCA)

코딩테스트에서 나오는 문제 중 하나인 LCS 구하기에 대해 공부해 보았다. 이 글의 내용은 Do it! 알고리즘 코딩테스트를 참고하였다.

 

최소 공통 조상이란?

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

 

최소 공통조상을 구하는 방법은 2가지가 있다.
일반적으로 구하는 방법과 빠르게 구하는 방법이다.
일반적으로 구하는 방법은 Depth를 하나씩 거슬러 올라가야 해서 모든 Depth를 탐색해야 할 수 도있다. 그래서 시간 복잡도가 크다. 하지만 빠르게 구하는 방법은 2의 K승 씩 올라가서 비교하면서 빠르게 구할 수 있다.

 

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

이건 책에 나오는 예제이다. 이 예제를 직접 그려서 설명을 할려고 한다.

 

1. 제일 처음 해야 하는 것은 각 노드의 부모 노드와 깊이를 저장해야 한다.

부모 노드와 깊이를 저장할 때 나는 주로 BFS를 사용하여 저장한다.

위의 트리를 깊이와 부모 노드를 찾으면 위의 표처럼 된다.

Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1); //루트 노드
depth[1] = 0; // 루트의 깊이는 0
parent[1] = 0; // 루트의 부모는 0
while(!dq.isEmpty()){ // BFS로 탐색하면서 부모와 깊이 찾아냄
    int now = dq.removeFirst(); 
    visited[now] = true;
    for(int i =0; i<tree[now].size(); ++i){
        int next = tree[now].get(i);
        if(visited[next]) continue;
        parent[next] = now;
        depth[next] = depth[now]+1;
        dq.addLast(next);
    }
}

 

2. 선택된 두 노드의 깊이가 다른 경우 깊이가 더 낮은 노드를 하나씩 올려주면서 깊이를 맞춘다. 이때 두 노드가 같으면 해당 노드가 LCA이므로 탐색을 종료한다.

이렇게 15에서 11, 11에서 6으로 갈 경우 4와 노드이 깊이가 동일해 졌다. 이제 여기서 부터 4와 6을 같이 하나씩 올리면서 깊이가 같아질 때 까지 반복한다.

이런 과정을 거쳐 LCA는 1이다.

public static int LCA(int u, int v){
    //depth 가 더 큰 것을 노드 하나씩 옮김
    while(true){
        if(depth[u] > depth[v]){ 
            u = parent[u];
        }
        else if(depth[u] < depth[v]){
            v = parent[v];
        }
        else break;
    }
    //depth가 같은 두 노드를 두 노드의 수 가 같아질 때까지 이동
    while(true){
        if(u == v) break;
        u = parent[u];
        v = parent[v];
    }
    return u;
}

 

참고 문제 : 백준_11437, LCA

11437번: LCA

 

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

일반 적인 LCA 구하기는 높이가 같은 노드를 찾을 때 한 단계씩 올려주지만 빠르게 구하기는 2의 K 제곱씩 올려준다. 

그래서 부모 노드를 저장할 때 2의 k 제곱 번째 위치의 부모 노드까지 저장해 주어야 한다.

 

1. 부모 노드 저장 배열 만들기

원래 parent는 parent[n+1]이지만 이제 최대 depth의 수 +1 이어야 한다. parent[depth+1][n+1]이다.

이런 트리가 있다고 할 때, 15의 깊이는 5이다. 15의 2의 0제곱 부모는 13, 2의 1제곱 부모는 11, 2의 2제곱 부모는 3이고 2의 3제곱 부모는 존재하지 않는다. 15개의 수가 한쪽 방향으로 만 있을 때 최대 2의4제곱 위의 부모까지 존재할 수 있으므로 parent배열의 가로축은 depth+1 까지 만든 것이다. 설명한대로 배열을 만들어 보면

이렇게 만들어 진다. 점화식을 살펴보면 P[K][N] = P[K-1][P[K-1][N]] 이다.

예시를 들어보면 12의 4번째 부모노드는 P[2][12] = P[1][P[1][12]] = P[1][6] = 1인 것이다.

 

dMax = 0;
//최대 Depth 구하기
while(temp <= n){ 
   temp <<= 1;
   dMax++;
}
parent = new int[dMax + 1][n+1];

//바로 위 부모 노드 구하기
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1);
while(!dq.isEmpty()){
    int now = dq.removeFirst();
    visited[now] = true;
    for(int i =0; i<arr[now].size(); ++i){
        int next = arr[now].get(i);
        if(visited[next]) continue;
        visited[next] = true;
        dq.addLast(next);
        parent[0][next] = now;
        depth[next] = depth[now]+1;
    }
}

//점화식을 통해 2의 제곱수 부모 구하기
for(int k =1; k <= dMax; k++){
    for(int s =1; s <= n; ++s){
        parent[k][s] = parent[k-1][parent[k-1][s]];
    }
}

 

 

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

parent 배열을 이용해 2의 K 제곱 단위로 넘어가면서 깊이를 맞춘다.

예를 들어 위 트리의 2와 15의 깊이를 맞춘다고 가정해보자. 그러면 2의 깊이는 1, 15의 깊이는 5이다. 둘의 깊이 차이는 4이므로 한번에 2의 제곱 부모를 찾으면 된다. 그러면 2와 3이 맞춰진다.

만약  높이 차가 20이면 2의 4제곱 부모 찾고 2의 제곱 부모를 찾으면 20위의 부모를 2번만에 찾을 수 있다.

 

3. 최소 공통 조상 찾기

높이를 맞췄으면 2의 K 단위로 점프하면서 부모를 찾는다. K가 0이 될 때 까지 반복한다. 반복이 끝난 후 두개의 노드가 같다면 해당 노드가 LCA이고 아니면 하나 바로 위의 부모가 LCA가 된다.

public static int LCA(int a, int b){
    //무조건 b의 노드가 depth가 큰 것으로 맞춘다.
    if(depth[a] > depth[b]){
        int temp = a;
        a = b;
        b= temp;
    }
    //2개의 노드의 depth 차를 이용해 깊이를 맞춘다.
    for(int k = dMax; k >= 0; k--){
        if(Math.pow(2, k) <= depth[b]-depth[a]){
            if(depth[a] <= depth[parent[k][b]]){
                b = parent[k][b];
            }
        }
    }
    //depth가 같은 순간 부터 두 노드의 공통 조상을 찾기 위해 2의 제곱수 만큼 씩 올라간다.
    for(int k = dMax; k >= 0; k--){
        if(parent[k][a] != parent[k][b]){
            a = parent[k][a];
            b = parent[k][b];
        }
    }
    int LCA = a;
    if(a != b) LCA = parent[0][LCA];
    return LCA;
}

 

참고 문제 : 백준_11438, LCA

11438번: LCA 2