11438번

11438번 - LCA2

이 문제는 저번에 풀다가 질문 게시판에 올렸는데, N의 max 값을 잘못봐서 계속 틀렸었다.

LCA 2 문제는 기존의 LCA 알고리즘보다, DP를 이용해서 문제를 푸는 방식으로 속도가 향상된다.

P[i][j] =노드 i 의 2^j번째 부모 라는 점화식을 세우면,

P[i][j] = P[P[i][j-1]][j-1] 이라는 식을 세울 수가 있다. ( 2^4=(2^2)*(2^2) ) 과 비슷한 원리!

따라서 로직은

1. 양방향 간선으로 입력을 받기.

2. 입력받은 값을 토대로, 임의의 루트(여기선 1)를 지정하고 BFS를 이용해서 트리를 만든다.

(이때, depth 값들을 저장, p[i][0] 은 parent[i] 와 같으므로 초기화를 시켜준다)

3. DP값을 바텀업 방식으로 채워준다.

4. LCA 알고리즘을 수행한다.

4-1. max_level 을 통해서 올라가면서 양쪽 노드의 높이를 맞춰준다.

4-2. max_level 을 통해서 함께 올라가면서 같지 않을 때까지 올라간다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
 
const int Max_Num = 100001;
const int max_level = (int)floor(log2(Max_Num));
int LCA(int a, int b, vector<vector<int>> &p,vector<int> &depth)
{
    //높이 맞추기
 
    if (depth[a] < depth[b])
    {
        swap(a, b);
    }
 
    if(depth[a] != depth[b])
    {
        for (int i = max_level; i >= 0; i--)
        {
            if (depth[p[a][i]] >= depth[b])
            {
                a = p[a][i];
            }
        }
    }
 
    if (a != b)
    {
        for (int i = max_level; i >= 0; i--)
        {
            if (p[a][i] != p[b][i] && p[a][i]!=0)
            {
                a = p[a][i];
                b = p[b][i];
            }
 
        }
 
        return p[a][0];
 
    }
    else
    {
        return a;
    }
 
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d", &n);
    vector<vector<int>> v(n + 1);
    vector<int> depth(n + 1, 0);
    vector<vector<int>> p(n + 1, vector<int>(max_level+1, 0));
    vector<int> ans;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    ////////////////bfs로 트리만들기(루트가 1)
 
    queue<int> q;
    depth[1] = 1;
    q.push(1);
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i];
            if (depth[next] == 0)
            {
                depth[next] = depth[now] + 1;
                //p초기화
                p[next][0] = now;
                q.push(next);
            }
        }
    }
    ////////////////////////
 
    for (int j = 1; j <= max_level; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (p[i][j - 1] != 0)
            {
                p[i][j] = p[p[i][j - 1]][j - 1];
            }
        }
    }
 
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        ans.push_back(LCA(a, b, p, depth));
    }
 
 
    for (int i = 0; i < ans.size(); i++)
    {
        printf("%d\n", ans[i]);
    }
 
    return 0;
}