Algorithm - LCA (최소 공통 조상)

개념

Lowest Common Ancestor의 약자로써 트리에서 가장 가까운 공통 조상을 찾는 알고리즘이다.

LCA

쉬운 방법으로 두 노드의 높이를 맞추고 하나씩 올라가면서 검사하는 방법이 있다. -> O(n)

 

시간 복잡도를 줄이는 방법

ancestor라는 2차원 배열을 만들고, ancestor[index][i] = index의 2^i 위에 부모노드를 저장하고 높이를 올릴 때 2^n단위로 올린다. -> O(logn)

 

ancestor[index][i] = ancestor[ancestor[index][i - 1][i - 1]

---

작동원리

1. DFS를 사용하여 각 노드의 Level과 ancestor배열을 초기화한다.

2. 높이가 깊은 노드의 높이를 2^n 단위로 올리면서 맞춘다.

3. 두 노드가 같은 뿌리에 있으면 v1 == v2가 되고 공통 노드를 찾게된다.

4. 두 노드가 같은 뿌리에 없는 경우 두 노드를 2^n 단위로 올리면서 공통 조상을 찾는다.

---

시간복잡도

초기화 할 때 DFS -> O(n)

공통 노드를 찾을 때 2^n단위로 올리기 때문에 -> O(logn)

---

문제

LCA 2

www.acmicpc.net/problem/11438

11438번: LCA 2

---

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n, MAX_DEPTH;
vector<int> depth;
vector<vector<int>> ac, graph;

void init(int now, int parent) {
    depth[now] = depth[parent] + 1;

    ac[now][0] = parent;
    for (int i = 1;i <= MAX_DEPTH;++i) {
        ac[now][i] = ac[ac[now][i - 1]][i - 1];
    }

    for (int &next : graph[now]) {
        if(next != parent) {
            init(next, now);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin >> n;
    MAX_DEPTH = (int)log2(n) + 1;
    ac.assign(n + 1, vector<int>(MAX_DEPTH + 1));
    graph.resize(n + 1);
    depth.resize(n + 1);
    for (int i = 1; i <= n - 1; ++i) {
        int v1, v2;
        cin >> v1 >> v2;

        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }

    init(1, 0);

    int m;
    cin >> m;
    while(m--) {
        int v1, v2;
        cin >> v1 >> v2;

        if(depth[v1] > depth[v2]) {
            swap(v1, v2);
        }

        for (int i = MAX_DEPTH;i >= 0;--i) {
            if (depth[ac[v2][i]] >= depth[v1]) {
                v2 = ac[v2][i];
            }
        }

        if(v1 == v2) {
            cout << v1 << "\n";
        }
        else {
            for (int i = MAX_DEPTH;i >= 0;--i) {
                if (ac[v1][i] != ac[v2][i]) {
                    v1 = ac[v1][i];
                    v2 = ac[v2][i];
                }
            }

            cout << ac[v1][0] << "\n";
        }
    }
}