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

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

최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다.

예시 트리

위와 같은 예시 트리 구조에서, 13, 15번 정점의 최소 공통 조상은 5번 정점이 된다. 마찬가지로,

13, 11번 정점의 최소 공통 조상은 1번 정점(Root)이 된다.

 

LCA를 선형 탐색으로 구하기 : O(Depth)

트리에서 이러한 최소 공통 조상을 찾으려면 어떤 방식을 사용해야 할까?

가장 단순한 방법으로는, 두 포인터를 두고 가리키는 정점이 같아질 때까지 부모 노드로 거슬러 올라가면 될 것이다.

즉 Parent[x]를 정점 x의 부모 노드라 할 때, x = Parent[x] 연산을 반복하면 될 것이다.

하지만 구하고자 하는 두 정점의 LEVEL(깊이)이 다르다면 문제가 발생한다.

11, 13번 정점의 최소 공통 조상을 찾는 상황을 생각해보자.

13번 정점에서 최소 공통 조상인 1번 정점까지는 4번을 거슬러 올라가야 하지만,

11번 정점에서는 3번을 거슬러 올라가면 도달할 수 있기 때문이다.

 

잠시 다른 예를 들어, 13번과 15번 정점의 최소 공통 조상을 구해보자. 최소 공통 조상은 5번 정점이다.

동시에 거슬러 올라간다면 원래 13번 정점을 가리키던 포인터가 5번 정점까지 도달한 순간,

원래 15번 정점을 가리키던 포인터는 2번 정점을 가리키게 된다. 

따라서 동시에 거슬러 올라가기 전, 두 정점의 깊이를 동일하게 맞춰야 한다.

다시 원래 문제로 돌아와서, 깊이를 맞춘 후 이제는 9번, 11번 정점의 최소 공통 조상을 구하는 문제로 바뀌었다.

두 정점의 깊이가 같기 때문에, 가리키는 정점이 같아질 때까지 동시에 거슬러 올라가면 된다.

11437번: LCA

 

[코드 : 위 문제의 해답 코드로 대체]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
 
vector<int> adj[100001];
int n, parent[100001], level[100001];
 
int lca(int a, int b) {
    //a를 더 level이 높은 정점으로 맞춘다.
    if (level[a] < level[b]) swap(a, b);
 
    //두 정점의 level을 같게 만들기
    while (level[a] != level[b]) {
        a = parent[a];
    }
 
    //가리키는 정점이 같아질 때까지 거슬러 올라가기
    while (a != b) {
        a = parent[a];
        b = parent[b];
    }
 
    return a;
}
 
void set_tree(int node, int pnode) {
    //DFS로 트리 구성
    parent[node] = pnode;
    level[node] = level[pnode] + 1;
 
    for (int i = 0; i < adj[node].size(); i++) {
        int child = adj[node][i];
        if (child == pnode) continue;
 
        set_tree(child, node);
    }
}
 
void init() {
    int f, s;
    cin >> n;
 
    for (int i = 0; i < n - 1; i++) {
        cin >> f >> s;
        adj[f].push_back(s);
        adj[s].push_back(f);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    set_tree(1, 0);
 
    int m, f, s;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> f >> s;
        printf("%d\n", lca(f, s));
    }
 
    return 0;
}

 

이 방법은 두 정점의 깊이에서부터 최대 root까지의 모든 정점을 선형으로 탐색해야 하므로, 시간 복잡도는 O(depth)가 된다.

 

LCA를 이분 탐색으로 구하기 : O(log(Depth))

위에서 살펴본 방법은 구현이 간단하지만 트리의 구조에 따라 시간적 측면에서 매우 비효율적일 수 있다.

예를 들어, 깊이가 50000, 50000인 두 정점에 대해 LCA를 구하려면 최대 50000번의 탐색이 필요하다. 이러한 질의가 10000개만 되어도 매우 긴 시간이 걸리게 된다.

우리는 이분 탐색을 통해 LCA를 더 빠른 log 시간 내에 구할 수 있다.

이제는 Parent 배열을 2차원으로 두어, Parent[x][k] = "x번 정점의 2^k번째 조상 노드의 번호" 로 둔다.

만약 DFS를 통해 Root부터 트리를 구성한다면, 낮은 깊이의 노드를 반드시 먼저 탐색하므로 다음이 성립한다.

Parent[x][k] = Parent[Parent[x][k - 1]][k - 1]

Parent[13][2] = Parent[Parent[13][1]][1]임을 확인할 수 있다.

이제 선형 시간에 구하는 방법에서 부모 노드로 거슬러가는 과정을 2의 제곱수만큼 한 번에 건너뛸 수 있다.

만약 13, 4번 정점의 최소 공통 조상을 구한다면, 13번 정점의 깊이를 4번 정점의 깊이로 맞추기 위해

5번 정점으로 바로 거슬러 올라간 뒤, 2번 정점으로 거슬러 올라갈 수 있다.

11438번: LCA 2

 

[코드 : 위 문제의 해답 코드로 대체]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
typedef pair<int, int> p;
 
int n, m;
vector<int> adj[100001];
int parent[100001][18];        //parent[i][j] : i번 노드의 2^j번째 조상
int level[100001], maxlevel;
 
void set_tree(int node, int pnode, int lv) {
    level[node] = lv;
    parent[node][0] = pnode;
 
    for (int i = 1; i <= maxlevel; i++) {
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
    }
 
    for (int i = 0; i < adj[node].size(); i++) {
        int childnode = adj[node][i];
        if (childnode == pnode) continue;
        set_tree(childnode, node, lv + 1);
    }
}
 
int LCA(int a, int b) {
    //a, b의 LCA를 찾아 반환
    if (a == 1 || b == 1) return 1;
 
    //a, b중 level이 더 높은 노드에 대해, 2^k번째 조상 노드를 찾아 올라간다.
    int target = a, compare = b;
    if (level[a] < level[b]) swap(target, compare);
 
    //두 노드의 level이 같아지도록 조정
    if (level[target] != level[compare]) {
        for (int i = maxlevel; i >= 0; i--) {
            if (level[parent[target][i]] >= level[compare])
                target = parent[target][i];
        }
    }
 
    //동일 level로 맞췄으므로, 공통 조상을 찾는다.
    int ret = target;
    if (target != compare) {
        for (int i = maxlevel; i >= 0; i--) {
            if (parent[target][i] != parent[compare][i]) {
                target = parent[target][i];
                compare = parent[compare][i];
            }
            ret = parent[target][i];
        }
    }
 
    return ret;
}
 
void init() {
    int p, c;
    cin >> n;
 
    for (int i = 0; i < n - 1; i++) {
        cin >> p >> c;
        adj[p].push_back(c);
        adj[c].push_back(p);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    maxlevel = (int)floor(log2(100001));
 
    set_tree(1, 0, 1);
 
    cin >> m;
    int f, s;
    for (int i = 0; i < m; i++) {
        cin >> f >> s;
        printf("%d\n", LCA(f, s));
    }
 
    return 0;
}

 

코드의 40번째 줄과 같이 가장 높은 깊이에서 높이를 감소시키며 확인하는 이유는 무엇일까?

정점 x, y의 LCA를 구하는 상황을 가정해 보자. x의 깊이가 y의 깊이보다 더 크다.

정점 x에서 2^k 번째 조상 노드로 거슬러 올라간 정점을 x'라 하자.

이 때 x'의 입장에서는 2^k번째 이상의 조상 노드는 확인할 필요가 없어진다.

x'로 올라온 이유는 x의 2^(k+1)번째 조상 노드의 깊이가 y의 깊이보다 작아졌기 때문에(너무 멀리 가버렸기 때문에) 그를 선택하지 않은 것이기 때문이다.

이러한 점을 한번에 확인하며 거슬러 올라가기 위해 최대 깊이에서 감소시키며 확인한다고 이해하면 된다.