[백준] 11438번 LCA2 (C++)

문제

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

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상(LCA, Lowest Common Ancestor)을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리를 구성하는 간선 정보가 주어진다. 각 줄에는 두 개의 정수가 주어지는데, 이는 해당 간선이 연결하는 두 정점을 의미한다.

다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

예제 입력 1

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15

출력

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

예제 출력 1

2
4
2
2
3
1

풀이

문제 해결 방법

이 문제는 LCA(Lowest Common Ancestor) 알고리즘을 최적화하여 해결할 수 있습니다. 주요 해결 단계는 다음과 같습니다:

1. 전처리:
   • DFS로 각 노드의 깊이와 2^k번째 조상을 계산
   • 희소 배열(Sparse Table)을 구성
2. LCA 찾기:
   • 두 노드의 깊이를 동일하게 맞춤
   • 공통 조상을 이진 탐색으로 찾음

이 알고리즘의 시간 복잡도는 다음과 같습니다:

• 전처리: O(N log N)
• 쿼리당: O(log N)

코드

#include<vector>
#include<stdio.h>
#include<algorithm>

using namespace std;

int n, m;
vector<int> mp[100001];
int depth[100001];
int parent[18][100001];

void dfs(int x, int d, int p)
{
    depth[x] = d;
    parent[0][x] = p;

    for (int next : mp[x])
    {
        if (next == p) continue;

        dfs(next, d + 1, x);
    }
}

int getLCA(int a, int b)
{
    //1. 둘의 높이를 맞춰줘야한다.
    // a 의 depth가 더 커서 b로 맞춰준다.
    if (depth[a] < depth[b]){
        swap(a, b);
    }

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

    if (a == b) return a;

    // 2. 조상으로 올라가면서 찾아가야해요.
    for (i = 17; i >= 0; i--)
    {
        if (parent[i][a] == parent[i][b]) continue;
        else
        {
            a = parent[i][a];
            b = parent[i][b];
        }
    }

    return parent[0][a];
}

int main()
{
    int i, j;
    int a, b;
    scanf("%d", &n);
    for (i = 1; i < n; i++)
    {
        scanf("%d%d", &a, &b);
        mp[a].push_back(b);
        mp[b].push_back(a);
    }

    // 1번 노드부터 시작해서 각 노드의 깊이와 parent를 구한다.
    dfs(1, 0, 0);

    for (i = 1; i <= 17; i++)
    {
        for (j = 1; j <= n; j++)
        {
            parent[i][j] = parent[i - 1][parent[i - 1][j]];
        }
    }

    scanf("%d", &m);

    for (i = 1; i <= m; i++)
    {
        scanf("%d%d", &a, &b);

        int lca = getLCA(a, b);

        printf("%d\n", lca);
    }

    return 0;
}