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

게시 2026/04/18

By kdHyeok

7 분읽는 시간

그래프 트리 LCA

문제

문제 링크

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

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

입력

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

출력

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

문제 조건

목표: N개의 노드로 이루어진 트리에서 M개의 노드 쌍에 대해 각각의 최소 공통 조상(LCA)을 오프라인으로 구한다.
입력 상태: 노드 수 N(≤50,000), 쿼리 수 M(≤10,000)이며 트리의 루트는 1번으로 고정되어 있다.
핵심 조건: Tarjan’s Offline LCA 알고리즘을 사용하므로 모든 쿼리를 미리 입력받아 저장해야 하며, DFS 방문 순서와 Union-Find의 집합 합치기 시점이 일치해야 정확한 조상을 찾을 수 있다.

풀이

핵심 알고리즘

그래프 이론

시간 복잡도: O((N + M) · α(N)) — N=50,000, M=10,000일 때 약 60,000번의 연산에 역 아커만 함수가 곱해진 수준으로 매우 효율적이다.

핵심 아이디어

Tarjan’s Offline LCA 알고리즘을 구현한다. DFS로 트리를 순회하며 자식 노드의 탐색이 끝날 때마다 Union-Find를 통해 자식을 현재 노드에 병합하고, 현재 노드와 관련된 쿼리 중 상대 노드가 이미 방문된 경우 Union-Find의 대표 원소를 통해 LCA를 즉시 확정한다.

① 오프라인 쿼리 수집

입력받은 M개의 쿼리를 각 노드의 인접 리스트 형식으로 저장한다. 이는 DFS 순회 도중 특정 노드(curr)를 방문했을 때, 해당 노드가 포함된 모든 쿼리를 즉시 확인하여 처리하기 위함이다.

  
    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 });
    }

② 후위 순회 기반의 트리 탐색 및 병합

DFS를 통해 트리를 하향 탐색하며, 자식 노드의 모든 서브트리 방문이 완전히 끝난 직후(후위 순회 시점)에 자식의 부모를 현재 노드로 업데이트한다. 이 과정을 통해 Union-Find 구조상에서 특정 노드의 조상은 현재 DFS가 머물고 있는 경로상의 노드로 수렴하게 된다.

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

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

③ Union-Find를 이용한 LCA 확정

현재 노드(curr)에서 연결된 쿼리들을 검사한다. 만약 쿼리의 상대 노드(target)가 이미 방문(visited) 상태라면, target 노드에서 find 연산을 수행했을 때 나오는 최상위 부모가 두 노드의 LCA가 된다. Path Compression을 적용한 find 함수를 사용해 효율성을 높였다.

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

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

성능

메모리 : 9116 KB
시간 : 24 ms

코드 (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;
}

algorithm