백준 11438번 C++ 풀이

문제

https://www.acmicpc.net/problem/11438

시간 제한	메모리 제한	solved.ac 티어
1.5초	256MB	플래티넘 5

사진을 클릭하면 문제로 이동합니다.

---

풀이

 밀린 문제 정리하기. LCA 알고리즘 편이다. 저번 문제에서는 O(n) LCA 로 풀 수 있는 문제였지만, 이 문제는 정말 불가능한 문제이다. 겸허히 O(log(N)) LCA를 사용해야 한다. O(n) LCA의 문제는 부모 노드로 이동하기 위해, 본인의 조상 노드를 하나씩 움직여야 하기에 선형시간이 걸리지만, 높이가 클 수록 비효율적일 것이다. 여기서 하나의 의문이 발생한다. 굳이 하나씩 다 이동해야 하는가?

 

 이를 해결하기위해 희소테이블을 사용한다. 트리의 데이터를 저장할때, 본인의 부모노드만 저장했지만, 희소테이블을 적용하여, i번째 노드의 2^0번째 부모, 2^1번째 부모, 2^2번째 부모....2^K번째 부모(K는 배열의 길이)를 저장한다. 이제 우리는 이 정보를 이용해 더 빠르게 부모노드로 이동할 수 있다. 어떤 노드의 163번째 조상을 알고 싶다고 하자. 원래라면 우리는 일일이 163번을 이동해야하지만, 163을 분해하면 163 = 128 + 32 + 2 + 1 = 2^7 + 2^5 + 2^1 + 2^0 임을 알 수 있다. 우리는 이러한 값들을 모두 저장해놨었기 때문에 4번의 이동으로 조상의 정보를 알 수 있다. 이를 적용한 것이 O(log(N)) LCA이다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define MAX_A 20 // log(max(n)) = log(100k) = 17이니 여유롭게 20으로 설정

int n,m;
vector<vector<int>> tree, graph;
vector<int> depths;
vector<pair<int,int>> query;

void make_tree(int st, int p, int h) {
    tree[st][0] = p, depths[st] = h;

    for(int g : graph[st]) {
        if (g == p) continue;
        make_tree(g, st, h+1);
    }
}

void make_ancestor() {
    for (int ancestor = 1; ancestor <= MAX_A; ancestor++) {
        for (int node = 1; node <= n; node++) {
            tree[node][ancestor] = tree[tree[node][ancestor - 1]][ancestor - 1];
        }
    }
}

void init(){
    make_tree(1, 0, 1);
    make_ancestor();
}

void input(){
    int a, b;
    cin >> n;
    graph.resize(n + 1);
    tree.resize(n + 1, vector<int>(MAX_A + 1));
    depths.resize(n + 1, -1);
    for (int i = 1; i < n; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cin >> m;
    query.resize(m);
    for(auto& [x, y] : query) {
        cin >> x >> y;
    }
    init();
}

void sol() {
    for(auto& [target, goal] : query) {
        // target노드를 goal노드의 높이로 끌어올린다.
        if (depths[target] < depths[goal]){
            swap(target, goal);
        }
        int dh = depths[target] - depths[goal];
        for (int i = MAX_A; i >= 0 && dh; i--) {
            if (dh >= (1 << i)) {
                target = tree[target][i];
                dh -= (1 << i);
            }
        }

        if (target == goal){
            cout << goal << endl;
        }
        else {
            for (int i = MAX_A; i >= 0; i--) {
                if (tree[target][i] != 0 &&
                    tree[target][i] != tree[goal][i]) {
                    target = tree[target][i];
                    goal = tree[goal][i];
                }
            }
        cout << tree[goal][0] << endl;
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    input();
    sol();
}