[Algorithm] 최소 공통 조상 (LCA. Lowest Common Ancestor)

최소 공통 조상 (LCA. Lowest Common Ancestor)

→ 두 정점이 만나는 최초 부모 정점을 찾는 것

트리 형식이 아래와 같이 주어졌다고 하자

4와 5의 LCA는? → 4와 5의 첫 부모 정점은 '2'

4와 6의 LCA는? → 첫 부모 정점은 root인 '1'

찾는 법

해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다.

[depth : 정점]
0 → 1(root 정점)
1 → 2, 3
2 → 4, 5, 6, 7

parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다.

// 1 ~ 7번 정점 (root는 부모가 없기 때문에 0)
const parent[] = {0, 1, 1, 2, 2, 3, 3}

이제 이 두 배열을 활용해서 두 정점이 주어졌을 때 LCA를 찾을 수 있다. 과정은 아래와 같다.

// 두 정점의 depth 확인하기
while (true) {
    if (depth가 일치)
        if (두 정점의 parent 일치?) LCA 찾음(종료)
        else 두 정점을 자신의 parent 정점 값으로 변경
    else // depth 불일치
            더 depth가 깊은 정점을 해당 정점의 parent 정점으로 변경(depth가 감소됨)
}

트리 문제에서 공통 조상을 찾아야하는 문제나, 정점과 정점 사이의 이동거리 또는 방문경로를 저장해야 할 경우 사용하면 된다.

 

최소 공통 조상 찾기

최소 공통 조상 찾기는 트리 구조에서 임의의 두 정점이 공통으로 갖는 가장 가까운 조상 정점을 찾는 문제다.

트리의 구조가 위의 예시와 같다면, 13과 15의 LCA는 5가 된다.

13과 11의 LCA는 1이 된다.

이 문제를 어떻게 해결할 수 있을까?

 

선형 탐색

가장 단순한 방법을 떠올려보자. 두 정점에서 시작해서 같아질 때까지 부모 노드로 거슬러 올라가면 될 것 같다.

여기서 주의해야할 점은 두 정점의 깊이가 다르다면 깊이를 맞춰줘야 한다.

위의 13과 15의 최소 공통 조상을 이 알고리즘을 통해 찾는다고 해보자. 깊이를 맞춰주지 않는다면 13은 부모인 9, 15는 부모인 5로 올라가고, 한 번 더 올라가면 둘은 깊이 차이 때문에 계속 엇갈려 결국 루트까지 올라가게 된다.

따라서 거슬러 올라가기 전에 일단 깊이를 동일하게 맞춰주고, 그 다음 가리키는 정점이 같아질 때까지 올라가면 된다.

부모로 올라가기 위해서 DFS를 통해 각 노드의 부모와 깊이를 저장해야 한다.

깊이를 따라 올라가기 때문에 O(Depth)의 시간복잡도를 가진다.

이분 탐색

“한 칸씩 올라가는건 너무 느리다”라는 생각에서 나온 아이디어로, 1칸씩 올라갔던 것을 1, 2, 4, 8, ...칸씩 올라감으로써 시간복잡도를 O(log Depth)로 줄일 수 있다. DP와 이분 탐색을 활용한다.

여러칸 올라가기 위해서는 부모를 저장한 배열에 1, 2, 4, 8, ... 칸 떨어진 부모가 누구인지 기록해야한다.

즉, 각 정점에 대해 1, 2, 4, ..번째(2^0, 2^1, 2^2, ... , 2^k-1) 부모의 정보를 기록한다. 이 배열을 parent라고 하면, parent[n][k]는 정점 n의 2^k 번째 조상을 의미한다. 여기서 k의 크기는 log2​n 의 올림이다. 왜냐하면 트리가 일자로 구성됐을때 2^k가 n보다 같거나 커야 끝까지 뛸 수 있기 때문이다.

먼저 DFS를 통해 첫 번째 부모를 저장하고 나서 2의 승수의 부모를 찾는다.

2의 승수 부모는 다음과 같은 아이디어를 통해 찾을 수 있다.

나를 기준으로 2칸 떨어진 부모는 1칸 떨어진 부모의 1칸 떨어진 부모다.

나를 기준으로 4칸 떨어진 부모는 2칸 떨어진 부모의 2칸 떨어진 부모다.

나를 기준으로 2^k-1칸 떨어진 부모는 2^k-1칸 떨어진 부모의 2^k-1부모다.

이 아이디어와 첫 번째 부모를 기록한 것을 통해 2칸, 4칸, ... 떨어진 부모를 차례대로 찾을 수 있다.

for (let k = 1; k < MAX; k++) { // Max는 Math.ceil(Math.log2(n))
    for (let node = 1; node <= n; node++)
        parent[node][k] = parent[parent[node][k - 1]][k - 1]
}

배열을 완성했다면 이제 공통 조상을 찾을 수 있다.

공통 조상을 찾는 과정은 선형 탐색에서 한 것처럼 깊이를 맞춰주고 정점이 같아질 때까지 올라가지만 과정이 좀 더 복잡하다.

1. 깊이 맞춰주기

두 정점 u와 v중 깊이가 더 깊은 것을 u라고 하자. 깊이 차는 깊이를 기록한 배열을 통해 쉽게 구할 수 있다. 이제 u를 v까지 점프시켜야 하는데, 이걸 어떻게 할까?

깊이 차가 5인 경우를 한 번 보자. 우리는 점프를 2의 승수로 하고 있다. 5를 2진수로 바꿔보면 101(2)가 된다. 이 뜻은 4칸 한 번, 1칸 한 번을 뛰면 같은 높이가 될 수 있다는 뜻이다.

즉 두 정점이 주어지면 두 정점의 높이 차를 구한 후, 비트 연산을 통해 깊이를 맞춰줄 수 있다.

function lca(u, v) {
    // u를 더 깊은 정점으로 함
    if(depth[u] < depth[v]) [u, v] = [v, u];
    let diff = depth[u] - depth[v];
    for(let hop = 1; diff !== 0; hop++) {
        if(diff & 1) u = parent[u][hop];
        diff >>= 1;
    }
}

2. 정점이 같아질 때까지 올라가기

이제 깊이가 같아졌으니 최소 공통 조상을 찾으면 된다. 선형 탐색에서는 현재 위치부터 점진적으로 올라갔지만, 여기서는 뛸 수 있는 최대 거리만큼 뛰고 밑으로 내려오면서 찾을 것이다.

두 정점에서 뛰었는데 부모가 동일하다면 ‘최소’ 공통 조상이 아닌 그냥 공통 조상을 찾은 것이다. 최소 공통 조상을 건너뛰었을 수도 있기 때문이다. 따라서 부모가 다를 때 각각 그 부모로 점프 시키면서 뛰는 거리를 절반씩 줄이면 두 정점의 위치는 LCA의 바로 아래가 된다.

위 예시에 알고리즘을 적용해보자.

먼저 13을 9로 올려 깊이를 맞춰준다. 트리의 노드 수가 15개이기 때문에 최대 뛸 수 있는 거리는 4다. 4만큼 뛰면 트리 범위를 넘어가니 무시하고, 절반을 줄인 거리인 2만큼 뛸 것이다. 9와 11에서 2만큼 뛰면 부모가 각각 2와 4다. 부모가 다르므로 각각 부모의 위치로 점프시킨다. 그 다음 1만큼 뛰면 부모가 1로 같으니 무시한다. 결과를 보면 두 정점이 LCA의 밑에 온 것을 확인할 수 있다.

function lca(u, v) {
    // 1. 깊이 맞추기
    // u를 더 깊은 정점으로 함
    if(depth[u] < depth[v]) [u, v] = [v, u];
    let diff = depth[u] - depth[v];
    for(let hop = 1; diff !== 0; hop++) {
        if(diff & 1) u = parent[u][hop];
        diff >>= 1;
    }
    
    // 2. LCA 찾기
    if(u === v) return u;

    for(let i = MAX - 1; i >= 0; i--) {
        // 부모가 트리 범위 안에 있고 다르다면 그 위치로 점프
        if(parent[u][i] !== -1 && parent[u][i] !== parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }   
    return parent[u][0];
}