[BOJ 5971] Meeting Place

백준 문제 링크

🔍 문제 분석

• 전형적인 LCA알고리즘을 이용하는 문제이다. 설명은 코드로 대신한다.

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX_N = 1000, MAX_DEPTH = 10;

int N, M, depth[MAX_N + 1], p[MAX_N + 1][MAX_DEPTH + 1];
vector<int> tree[MAX_N + 1];

void init() {
    for (int i = 1; i <= MAX_DEPTH; ++i) {
        for (int j = 1; j <= N; ++j) {
            p[j][i] = p[p[j][i - 1]][i - 1];
        }
    }
}

void bfs() {
    memset(depth, -1, sizeof(depth));
    queue<int> q;
    q.push(1);
    depth[1] = 0;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (auto next : tree[curr]) {
            if (depth[next] != -1) continue;
            q.push(next);
            depth[next] = depth[curr] + 1;
        }
    }
}

int LCA(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);

    for (int i = MAX_DEPTH; i >= 0; --i) {
        if (depth[u] <= depth[p[v][i]]) v = p[v][i];
    }

    if (u == v) return u;

    for (int i = MAX_DEPTH; i >= 0; --i) {
        if (p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }

    return p[u][0];
}

int main() {
    fastio;

    cin >> N >> M;
    p[1][0] = 1;
    for (int i = 2; i <= N; ++i) {
        cin >> p[i][0];
        tree[p[i][0]].push_back(i);
    }
    init();
    bfs();
    while (M--) {
        int u, v;
        cin >> u >> v;
        cout << LCA(u, v) << "\n";
    }
}

📝 코드 설명

🔧 트러블 슈팅

📚 참고자료