BOJ 11437 - LCA(Tree)

www.acmicpc.net/problem/11437

11437번: LCA

- 트리에서 제시된 노드 2개 간의 가장 가까운 공통 조상을 찾는 알고리즘을 LCA 알고리즘 라고 부른다. (lowest common ancestor)

딱히 이진트리가 아니므로, 가변벡터의 트리배열을 선언하고 여기에 노드들을 담는다.

해당 노드의 레벨, 부모 정보를 담을 벡터를 선언하고,  각각의 노드의 부모를 찾기 위한 bfs탐색을 위해 방문여부 체크벡터도 선언한다. 

- LCA 알고리즘은 생각보다 간단한데, 각각의 노드의 부모와 레벨을 알고 있을 때, 두 노드의 레벨이 같을 때까지 한쪽 노드의 부모를 찾고,

레벨이 같아지면 parent가 같아질 때까지 동시에 순차적으로 한 칸씩 트리 위로 올라가면 된다.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, m;
vector<int> tree[50001];
vector<int> depth(50001);
vector<bool> check(50001);
vector<int> parent(50001);

int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);  // 노드u의 레벨이 항상 더 크다고 가정
    }
    while (depth[u] != depth[v]) {
        u = parent[u];
    }
    while (u != v) {
        u = parent[u];
        v = parent[v];
    }

    return u;
}

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

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    depth[1] = 0;  // 1번 노드가 루트
    check[1] = true;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : tree[x]) {
            if (check[y]) continue;
            depth[y] = depth[x] + 1;
            check[y] = true;
            parent[y] = x;
            q.push(y);
        }
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    return 0;
}