[백준] 11437번 : LCA (C++)

11437번 : LCA

---

문제)

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

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<vector<int>> vec;
int parent[50010];
int depth[50010];
bool check[50010];
 
void dfs(int cur, int deep)
{
    // 해당 노드의 깊이가 확인되었는지 확인
    check[cur] = 1;
    // 해당 노드의 깊이를 저장한다.
    depth[cur] = deep;
 
    for (auto nxt : vec[cur])
    {
        if (check[nxt]) continue;
        parent[nxt] = cur;
        dfs(nxt, deep + 1);
    }
}
 
// lca 알고리즘 / 같은 깊이로 먼저 맞춘 다음에.
// 이후부터 같은 조상을 찾는다.
// (이 lca 알고리즘은 가장 기본적인 형태의 lca임)
int lca(int a, int b)
{
    while (depth[a] != depth[b])
    {
        if (depth[a] > depth[b])
        {
            a = parent[a];
        }
        else
        {
            b = parent[b];
        }
    }
 
    while (a != b)
    {
        a = parent[a];
        b = parent[b];
    }
    
    return a;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    vec.resize(n + 1, vector<int>());
 
    int a, b;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    
    // 루트노트부터 내려가면서 해당 노드의 부모 노드를 찾는다.
    dfs(1, 0);
 
    int m;
    cin >> m;
 
    int x, y;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
 
    return 0;
}
 

 

참고하면 좋을 영상

https://youtu.be/O895NbxirM8

 

---

출처 : https://www.acmicpc.net/problem/11437 

11437번: LCA