[Baekjoon] 11437번: LCA (Gold) - C++ 풀이

그래프 이론 트리 최소 공통 조상

💾 메모리: 9116 KB, 시간: 24 ms📅 2026년 4월 9일 03:42:23

문제 링크

문제 설명

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

코드 (C++)

#include <iostream>
#include <vector>

using namespace std;

int parent[50001];
bool visited[50001];
vector<int> adj[50001];
vector<pair<int, int>> queries[50001];
int answers[100001];

// 표준 Path Compression
int find(int tar) {
    if (tar == parent[tar]) return tar;
    return parent[tar] = find(parent[tar]);
}

void LCA(int curr) {
    visited[curr] = true;

    for (int next : adj[curr]) {
        if (!visited[next]) {
            LCA(next);
            // 자식 탐색 완료 후, 자식의 부모를 현재 노드로 설정
            parent[next] = curr; 
        }
    }

    // 현재 노드와 관련된 쿼리 처리
    for (auto& q : queries[curr]) {
        int target = q.first;
        int queryIdx = q.second;

        if (visited[target]) {
            // target이 속한 집합의 최상단 부모가 LCA
            answers[queryIdx] = find(target);
        }
    }
}

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

    int N, M;
    if (!(cin >> N)) return 0;

    for (int i = 1; i <= N; i++) parent[i] = i;

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

    if (!(cin >> M)) return 0;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        queries[u].push_back({ v, i });
        queries[v].push_back({ u, i });
    }

    LCA(1);

    for (int i = 0; i < M; i++) {
        cout << answers[i] << "\n";
    }

    return 0;
}