[BOJ 3584] 가장 가까운 공통 조상

문제

www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

 

---

풀이

LCA(Lowest Common Ancestor)를 사용합니다.

사실 이번 문제는 전에 풀었던 11438 - LCA 2문제와 거의 다를 것이 없습니다.

다만, 다른 점이라면 루트노드가 따로 주어지지 않기 때문에 직접 찾아야한다는 것입니다.

하지만 그건 어렵지 않습니다.

​

먼저, 각 테스트케이스별 간선들의 정보를 입력받은 다음 노드 하나를 무작위로 골라서 더 이상 못 올라갈 때까지 올라갑니다.

더 이상 못 올라가는 상황이 될 때의 노드가 루트 노드가 됩니다.

 

루트 노드를 구하고 나면 LCA로 문제를 풀면 됩니다.

(참고: 백준 11438 - LCA 2 풀이)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int MAX_LVL = 30;

int N, root;
vector<vector<int>> graph;
vector<vector<int>> par;
vector<int> depth;

void find_root(int cur) {
    if (par[cur][0] == 0) {
        root = cur;
        return;
    }
    find_root(par[cur][0]);
}

void solve(int cur, int pnode) {
    depth[cur] = depth[pnode] + 1;
    par[cur][0] = pnode;

    for (int i = 1; i <= MAX_LVL; ++i)
        par[cur][i] = par[par[cur][i - 1]][i - 1];

    for (int i = 0; i < graph[cur].size(); ++i) {
        int next = graph[cur][i];
        if (next != pnode)
            solve(next, cur);
    }
}

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

    int T;
    cin >> T;
    while (T--) {
        int pnt;
        cin >> N;
        graph.clear();
        graph.resize(N + 1);
        par.clear();
        par.resize(N + 1, vector<int>(MAX_LVL + 1, 0));
        depth.clear();
        depth.resize(N + 1, 0);
        for (int i = 0; i < N - 1; ++i) {
            int a, b;
            pnt = a;
            cin >> a >> b;
            graph[a].push_back(b);
            par[b][0] = a;
        }

        find_root(pnt);
        solve(root, 0);

        int a, b;
        cin >> a >> b;
        if (depth[a] != depth[b]) {
            if (depth[a] > depth[b])
                swap(a, b);
            for (int i = MAX_LVL; i >= 0; --i)
                if (depth[a] <= depth[par[b][i]])
                    b = par[b][i];
        }

        int lca = a;
        if (a != b) {
            for (int i = MAX_LVL; i >= 0; --i) {
                if (par[a][i] != par[b][i]) {
                    a = par[a][i];
                    b = par[b][i];
                }
                lca = par[a][i];
            }
        }

        cout << lca << "\n";
    }

    return 0;
}