[BOJ알고리즘, C++]#11438_LCA 2, Binary Lifting

 

#1. 문제

 

11438번: LCA 2

 

---

 

#2. 풀이

 

1. 트리

 

[자료구조]#5_트리

 

트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리는 노드와 간선으로 이루어져 있으며, 노드 간의 연결 관계는 간선으로 나타냅니다. 트리 자료구조는 비 순환 구조이며, 노드 간 계층 구조를 갖는 것이 특징입니다.

 

2. LCA 알고리즘

 

[알고리즘]#7_LCA(Least Common Ancestor)

 

LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 두 노드의 가장 가까운 공통 조상이란, 두 노드의 공통 조상 중 깊이가 가장 깊은 조상 노드를 의미합니다. LCA 알고리즘은 Binary Lifting 기법을 활용하며, 이는 트리의 각 노드의 깊이, 부모 노드 정보를 통해 깊이가 깊은 트리 자료구조에서 LCA를 효율적으로 찾아냅니다.

 

3. 깊이가 깊다면! 부모 노드의 정보를 2차원 컨테이너에 기억한다!

 

1. 먼저, DFS를 수행하며 각 노드의 부모 노드와 깊이 정보를 업데이트합니다. 이때, Binary Lifting 기법을 활용하여, 부모 노드의 정보는 2차원 컨테이너에 저장한다! col 값은 현재 위치로부터 2*i 만큼 위에 위치한 조상 노드를 의미한다.
2. LCA 알고리즘을 통해, 주어진 두 노드의 LCA를 찾습니다!

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 100001
#define LOG2_MAX 18 // log2(MAX)

int N, M;
vector<int> graph[MAX];
int depth[MAX];
int parent[MAX][LOG2_MAX];

void dfs(int node, int parent_node)
{
    depth[node] = depth[parent_node] + 1;
    parent[node][0] = parent_node;
    for (int i = 0; i < graph[node].size(); i++)
    {
        int next = graph[node][i];
        if (next == parent_node)
            continue;
        dfs(next, node);
    }
}

void fillParent()
{
    for (int j = 1; j < LOG2_MAX; j++)
    {
        for (int i = 1; i <= N; i++)
        {
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }
}

int LCA(int a, int b)
{
    if (depth[a] > depth[b])
        swap(a, b);
    for (int i = LOG2_MAX - 1; i >= 0; i--)
    {
        if (depth[b] - depth[a] >= (1 << i))
        {
            b = parent[b][i];
        }
    }
    if (a == b)
        return a;
    for (int i = LOG2_MAX - 1; 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_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1, 0);
    fillParent();

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

    return 0;
}

 

---