LCA(Lowest Common Ancestor)

1개 이상의 노드로 구성 된 사이클이 없는 그래프를 트리라고 합니다.

우리는 트리에서 정의되는 LCA(Lowest Common Ancestor)에 대해서 얘기해 보려 합니다.

LCA를 직역하면 최소 공통 조상(?) 정도의 뜻으로 해석되며 두 정점에서 (자신을 포함한)조상들을 거슬러 올라갈 때 처음으로 공통되게 만나는 정점을 지칭합니다.

예를 들기 위해 다음과 같은 트리가 존재한다고 합시다.

이 트리에서 6번 정점과 10번 정점의 LCA를 구하면 

다음과 같이 2번 정점이 6번 정점과 10번 정점의 LCA가 됩니다.

이번에는 7번 정점과 10번 정점의 LCA를 구해보겠습니다.

다음과 같이 1번 정점이 7번 정점과 10번 정점의 LCA가 됩니다.

자, 이제 어느정도 LCA의 정의에 대한 감이 오시나요? 마지막으로 4번 정점과 12번 정점의 LCA를 구해보겠습니다.

4번 정점과 12번 정점의 LCA는 4번 정점이 됩니다. 우리는 두 정점 A,B의 LCA를 구할 때 A가 B에 조상이라면 LCA(A,B)=A가 된다는 사실을 알게됬습니다.

자 이제 LCA의 정의에 대해 알게 됬으니 구현을 해볼 차례입니다.

어떤 방식으로 구현을 할수 있을까요?

우리는 LCA를 구하는 두 정점의 높이(깊이)를 동등하게 맞춰준 후 동시에 조상을 탐색하면서 LCA를 구해줄 수 있습니다.

예를들어 7번 정점과 10번 정점의 LCA를 구한다면 7번 정점의 깊이는 2이고 10번 정점의 깊이는 3이므로 10번 정점의 깊이를 2에 맞춰주어 5번 정점을 보게합니다.

다음 그림과 같이 동일한 깊이인 5번 정점과 7번 정점을 이제 부모를 따라가면서 공통된 조상을 찾을 때 까지 바텀 업 하면 LCA를 찾을 수 있습니다.

이러한 방식으로 7번 정점과 10번 정점의 LCA가 1번 정점이라는 걸 알 수 있습니다.

이러한 방식으로 구현 했을 경우 시간 복잡도는 어떻게 될까요?

우리는 DFS 한번으로 자신의 부모와 깊이에 대한 전처리를 해줄 수 있습니다.

이후 LCA를 한번 구할때 마다 최악의 경우 정점의 개수에 비례하게 높이를 맞추니 O(N)의 시간복잡도를 가지게 됩니다.

다음과 같은 트리에서 LCA(1,N)을 구하는 쿼리는 O(N)의 시간복잡도를 가지게 됩니다.

하지만 LCA2와 같은 문제에서 O(N)에 쿼리를 처리한다면 우리는 O(N*M)의 시간복잡도를 가지고 시간초과를 보게 될 것입니다.

쿼리의 개수인 M을 조절해 줄 수는 없으니 적어도 LCA를 O(logN)의 시간복잡도에 구해줄 무언가가 필요합니다

우리는 O(N)의 방식으로 LCA를 구하는 방법을 약간 변형 시켜서 O(logN)의 시간복잡도에 LCA를 구해보겠습니다.

우선 전처리가 필요한데요. O(N)의 방식으로 dfs를 돌리면서 각 정점의 깊이와 부모를 저장합니다.

이때 미리 말하자면 우리는 한 정점의 2^N의 부모를 저장할 것이기 때문에 par[x][i] 배열(x: 정점번호 i: 2^i번째 조상을 의미)을 선언 한뒤 par[x][0]에 부모를 채워줍니다. 

DFS에 의한 전처리가 끝나면 반복문을 이용하여 각 정점들의 (2^i)번째 조상을 채워줄 것입니다.

이는 par[x][i]=par[par[x][i-1]][i-1]이라는 수식을 이용하면 채울 수 있습니다.

void dfs(int here,int depth) {
    visited[here] = true;
    d[here] = depth;
    for (int there : vt[here]) {
        if (visited[there])
            continue;
        par[there][0] = here;
        dfs(there, depth + 1);
    }
}
void f() {
    for (int j = 1; j < 21; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
}r

전처리에 대한 소스코드는 이정도가 되겠군요.

j를 왜 20까지 구하냐고 물으신다면 N이 10만이기 때문에 2^20은 100만 이상의 수로 2^20번째 조상까지만 채워주더라도 충분하기 때문입니다.

자 이제 2^i번째 조상들을 저장하여 이것을 어떻게 이용할 것이냐고 물어보면 아까와 같은 행동을 반복할것입니다.

LCA를 구하려는 두 정점의 높이를 맞춰준 후 똑같이 올라가며 LCA를 구할 것입니다.

단 우리는 2^i번째 조상들을 구해놨기 때문에 2^i만큼씩 지수승 씩 높이를 증가시킬 수 있습니다.

 

다음과 같은 트리가 존재할 때 16번 노드와 13번 노드의 LCA를 구해보겠습니다.

16번 정점의 깊이는 6이고 13번 정점의 깊이는 4입니다.

우리는 두 노드의 높이를 맞춰줄 때도 2^i 씩 거슬러 올라갈 수 있습니다. 두 정점의 깊이차가 X라면 

우리는 반복문을 통하여 (i=20 ~> 0) 2^i가 X보다 작아지는 순간 깊이가 깊은 정점을 par[v][i]로 갱신해 줌으로서 2^i씩 거슬러 올라갈 수 있습니다.

위의 그림 같은 경우에는 i가1일 때 2^1번째 부모로 갱신되어 12번 정점과 13번 정점 (깊이가 4로 같음)을 보게 되겠군요. 

현재 보고 있는 두 정점의 높이를 맞춘후에는 lca를 확인하기 위해 서로의 조상을 비교하는 작업도 2^i씩 거슬러 올라갈 수 있습니다.

반복문을 통하여(i=20~>0) 2^i번째 조상이 서로 달라지는 순간 2^i번째 조상으로 동시에 점프하게 됩니다.

아래 그림과 같이 12번 정점과 13번 정점의 조상은 2^2(=4)번째 조상까지는 같지만 2^1(=2)번째 조상은 서로 달라지게 되므로 2^1칸씩 거슬러 올라가 각각 6번 정점과 7번 정점을 보게 됩니다.

그 다음 반복문에 의하여 2^0(=1)번째 조상도 서로 다르므로 6번 정점과 7번 정점은 각각 2번 정점과 3번 정점을 보게 됩니다.

이후 반복문이 끝났고 내가 현재 확인하고 있는 두 정점 중 아무정점이나 상관없이 첫번째 부모가 두 정점의  LCA가 됩니다.

즉 16번 정점과 13번 정점의 LCA는 1번 정점이 되겠군요.

하지만 만약 두 정점의 높이를 맞췄을 때 두 정점이 같아진다면 그때는 두 정점중 아무 정점의 첫번째 부모가 아닌 정점 자체가 LCA가 됩니다.

이를 유의하여 LCA 코드를 작성하면

int lca(int x, int y) {
    if (d[x] > d[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (d[y] - d[x] >= (1 << i)) 
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}

이런 소스를 얻을 수 있습니다. 

감이 잘 안올수도 있는 분들을 위하여 LCA 2 소스도 첨부하겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 100000
using namespace std;
int n, m, par[MAX_N + 1][21], x, y, visited[MAX_N + 1], d[MAX_N + 1];
vector<vector<int>> vt;
void dfs(int here,int depth) {
    visited[here] = true;
    d[here] = depth;
    for (int there : vt[here]) {
        if (visited[there])
            continue;
        par[there][0] = here;
        dfs(there, depth + 1);
    }
}
void f() {
    for (int j = 1; j < 21; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (d[y] - d[x] >= (1 << i)) 
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
int main() {
    scanf("%d", &n);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &x, &y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    dfs(1, 0);
    f();
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}

이제 우리는 LCA를 O(logN)의 시간 복잡도에 계산할 수 있게 되었습니다.

그러면 LCA를 통하여 무엇을 할 수 있을까요?

트리에서 두 정점 사이의 거리를 빠르게 계산하거나 두 정점 사이를 연결하는 간선들의 가중치의 최솟값과 최댓값들을 저장하여 계산할 수도 있습니다.

이제 LCA를 활용하여 다양한 문제를 풀어봅시다!