C++ 코딩테스트 강좌, 최소 공통 조상 구하기 2

문제 설명

주어진 N개의 노드와 N-1개의 간선으로 이루어진 트리가 있습니다. 각 노드는 1부터 N까지의 정수로 번호가 매겨져 있습니다. 두 개의 노드 A와 B가 주어질 때, 이 두 노드의 최소 공통 조상(LCA, Lowest Common Ancestor)을 찾는 문제입니다. 단, 이 문제는 트리가 매우 클 수 있기 때문에, 효율적인 알고리즘을 이용해야 합니다.

입력

첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄에는 N-1개의 간선 정보가 주어진다. 각 간선은 “부모 자식”의 형태로 주어진다.
셋째 줄에는 LCA를 찾고자 하는 쿼리의 개수 Q (1 ≤ Q ≤ 100,000)와 각 쿼리에 대해 A, B가 주어진다.

예제 입력

예제 출력

2
1
3

해결 전략

최소 공통 조상을 효율적으로 찾기 위해서는 다음과 같은 접근 방식을 사용할 것입니다.

트리 구조의 표현: 트리는 인접 리스트를 사용하여 표현됩니다. 각 노드는 부모와 자식으로 연결되어 있으므로, 이를 바탕으로 트리를 구성합니다.
DFS를 통한 깊이 배열과 부모 배열 생성: DFS(Depth First Search) 알고리즘을 사용하여 각 노드의 깊이를 구하고, 부모 노드를 기록합니다. 이 정보는 LCA를 찾는 데 필수적입니다.
이진 제안법: LCA를 효율적으로 찾기 위해 이진 제안법(Fast LCA)을 사용합니다. 두 노드의 깊이를 맞추고, 같은 조상을 찾는 방식으로 진행됩니다.

구현 단계

1. 트리 구조 만들기

먼저 간선 정보를 바탕으로 트리를 구축합니다. 이 과정에서는 부모와 자식 간의 관계를 정의하며, 이를 인접 리스트를 통해 표현합니다.

2. DFS로 깊이 및 부모 배열 생성하기

이제 DFS를 사용하여 각 노드의 깊이와 부모를 기록해야 합니다. 깊이는 각 노드가 루트에서 얼마나 떨어져 있는지를 나타내고, 부모는 다음 단계에서 LCA를 찾는 데 필수적입니다.

3. LCA 함수 구현하기

이진 제안법을 사용하여 두 노드의 최소 공통 조상을 찾는 함수를 구현합니다. 이 함수는 두 노드의 깊이를 비교하고, 필요에 따라 깊이를 맞춘 후 조상을 찾아가는 방식입니다.

4. 쿼리 처리하기

쿼리에서 주어진 두 노드 A와 B에 대해 LCA를 찾아 출력합니다.

코드 구현

#include 
#include 
#include 
#include 

using namespace std;

const int MAX_N = 100000;
const int LOG = 17; // log2(100000) ≈ 16.61

int parent[MAX_N + 1][LOG + 1]; // 부모 배열
int depth[MAX_N + 1];            // 깊이 배열
vector tree[MAX_N + 1];     // 인접 리스트 형식의 트리
int N;

void dfs(int node, int par, int d) {
    depth[node] = d;
    parent[node][0] = par;
    for (int i = 1; i <= LOG; i++) {
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
    }
    
    for (int child : tree[node]) {
        if (child != par) {
            dfs(child, node, d + 1);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    for (int i = LOG; i >= 0; i--) {
        if (depth[parent[a][i]] >= depth[b]) {
            a = parent[a][i];
        }
    }

    if (a == b) return a;

    for (int i = LOG; i >= 0; i--) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.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);
    }

    dfs(1, 0, 0); // 루트는 1
    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }

    return 0;
}

마무리

이 문제는 최소 공통 조상을 찾기 위해 DFS와 이진 제안법을 사용하는 방법을 잘 이해하는 데 도움을 줍니다. 트리를 처리하는 다양한 알고리즘을 익히고, 효율적인 코딩 능력을 기르는 데 큰 도움이 될 것입니다. 주어진 문제를 기반으로 다양한 방식으로 트리 구조를 탐색하고 LCA를 찾는 방법을 연습하면, 코딩테스트 준비에 매우 유용할 것입니다.