[BOJ알고리즘, C++]#11437_LCA

 

#1. 문제

 

11437번: LCA

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

 

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

 

2. LCA 알고리즘

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

 

LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 이때, 두 노드의 공통 조상 노드 중 깊이가 가장 깊은 조상 노드를 의미합니다. LCA 알고리즘은 Binary Lifting 기법을 활용합니다. Binary Lifting 기법은 트리 자료구조의 각 노드의 깊이, 그리고 부모 노드를 2의 승수로 저장하여 깊이가 깊은 트리 자료구조에서 효율적입니다.

 

3. 깊이가 깊지 않으면? 부모 노드 정보는 1차원 컨테이너에!

 

1. 먼저, DFS를 통해 트리의 루트 노드를 출발점으로 설정하고, 각 노드에 대한 깊이 값을 저장하고, 부모 노드의 정보를 업데이트합니다.
2. 다음으로, 주어진 두 노드에 대하여 LCA 알고리즘을 수행하고 결과를 출력합니다.

 

---

 

#3. 코드

 

/*
    @문제 : 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 찾기, LCA 알고리즘
    @설명
            1. DFS를 통해 트리의 각 노드에 대한 깊이 값을 찾습니다. 이 과정에서 각 노드의 부모 노드 또한 찾습니다.
            2.위에서 구한 깊이 정보를 통해 더 깊이 있는 노드를 부모 노드 방향으로 이동하며, 두 노드의 깊이 값을 맞춥니다.
            3.두 노드의 깊이가 동일해지면,두 노드가 같은 노드가 될 때까지 부모 노드 방향으로 이동 시키고, 두 노드가 만나는 지점이 두 노드의 LCA가 됩니다.

    @추가 설명

            1. um 대신 vector 활용 : vector 컨테이너가 캐시 효율이 um보다 뛰어나다.
*/

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

int N, M;
unordered_map<int, vector<int>> tree;
vector<int> depth, parent;
vector<bool> visited;
queue<int> q;

int LCA(int u, int v)
{
    // #1. 항상 v가 u보다 더 깊은 노드로 설정
    if (depth[u] > depth[v])
        swap(u, v);

    // #2. 두 노드의 깊이를 맞춰줍니다. v노드를 부모 노드방향으로 이동
    while (depth[u] != depth[v])
        v = parent[v];

    // #3. 두 노드를 부모 노드 방향으로 이동시키며, 가장 가까운 공통 조상을 찾습니다.
    while (u != v)
    {
        u = parent[u];
        v = parent[v];
    }

    return u;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    depth.resize(N + 1, 0);
    parent.resize(N + 1, -1);
    visited.resize(N + 1, false);

    for (int i = 0; i < N - 1; ++i)
    {
        int u, v;

        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    visited[1] = true;
    q.push(1);

    // #1. BFS를 통해 각 노드의 부모 노드, 깊이를 초기화합니다.
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (const auto &node : tree[cur])
        {
            if (!visited[node])
            {
                visited[node] = true;
                depth[node] = depth[cur] + 1;
                parent[node] = cur;
                q.push(node);
            }
        }
    }

    cin >> M;

    for (int i = 0; i < M; ++i)
    {
        int u, v;

        cin >> u >> v;

        cout << LCA(u, v) << '\n';
    }

    return 0;
}

 

---