백준 11438 LCA 2

트리를 입력받은 뒤, 공통 조상 중 가장 가까운(높이가 낮은) 노드를 찾는 문제이다. LCA 1이 있고 LCA 2가 있는데, LCA 1은 나이브하게 공통 조상을 밑에서부터 같이 찾아 올라가도 정답 처리가 되지 않을까 싶다. 그 문제는 골드3이고 이 문제는 플레 5이므로 난이도 차이가 꽤 난다. 

 

문제의 접근은 DP-Like 하다. DP도 제대로 본건 아니지만, 연산 과정을 배열에 저장한다는 관점에선 비슷하다고 볼 수 있지 않을까? DP를 좀 더 많이 해보고 차이점을 더 잘 알게 된다면 이 글을 수정해야겠다.

그럼 여기서 DP-Like 하게 연산과정을 저장한다고 했는데, 무엇을 저장하는가? 바로 어떤 노드의 2^K번째 조상을 저장한다. 100000개의 노드가 있을 때, Worst Case일 경우 높이는 100000이다. ceil(log2(100000)) = 18이므로, 저장하는 데이터 수를 획기적으로 감소시킬 수 있다.

---

솔루션의 흐름은 다음과 같다.

1. 각 노드가 연결되는것을 입력받고 adj(인접 행렬)을 만든다.
2. 2^K번째 부모가 저장되는 parents 배열과 depth 배열을 -1 값을 가지도록 초기화한다.
3. DFS로 Depth와 초기 Parents배열 값을 넣어준다(2^0 = 1, 바로 위 부모 노드를 넣어준다)
4. K를 0부터 MAX - 1까지 돌면서 Parents[K+1][V] 값을 넣어 Parents 배열을 완성시켜준다.
   1. 2^(K + 1) = 2 * 2^K 이므로, V의 2^K 번째 조상의 2^K 번째 조상을 2^(K + 1) 번째 조상 자리에 넣어준다.
5. LCA를 구할 두 노드 u ,v를 입력 받고, 높이를 맞춰준다.
   1. Depth 차이 Diff를 2진수로 보고, 2진수의 각 자리가 1일때 그 자리수만큼 parents배열에서 구해다가 대입해주면 그만큼 올라간다.
   2. Diff = 11일 경우, 2진수로 1011이다. 2^0, 2^1, 2^3일때 1이므로, u = parents[0][u], u = parents[1][u], u = parents[3][u]가 실행되어 11만큼 올라가게 된다.
6. 이제 u와 v 가 같은 높이이므로 똑같이 위로 올라가며 탐색해서 최소 공통 조상을 찾는다.
   1. K를 맨 위부터 시작해서 내리며 탐색한다. u와 v의 2^K 번째 조상이 달라질때까지 K를 감소하여 탐색한다
   2. u와 v의 2^K 번째 조상이 달라지면, u와 v를 각 조상으로 대치한다.
   3. K가 0일때까지 반복.
7. 다 돌고 나면 LCA 바로 밑 갈라진 u, v 상태이다. u나 v의 바로 위 조상을 찾으면 LCA이다!

더 자세한 설명은 LCA 포스팅을 따로 올렸으므로 그쪽을 보면 더 이해가 잘 될것 같다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <string.h>
const int MAX = 18; //log2(100000) 올림

int parents[MAX][100000];
int depth[100000];
void initTree(int cur_node, std::vector<int> adj[])
{
    for (int i = 0 ; i < adj[cur_node].size(); i++)
    {
        int next = adj[cur_node][i];
        if(depth[next] == -1) //다음 탐색할 노드가 값이 안들어가있는 경우 (자식인 경우)
        {
            depth[next] = depth[cur_node] + 1;
            parents[0][next] = cur_node;
            initTree(next, adj);
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0) ; // 입출력 Timeout
    int N;
    std::cin >> N;
    std::vector<int> adj[N];

    for (int i = 0; i < N -1 ; i++)
    {
        int a, b;
        std::cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    //int max_h = std::ceil(log2(N));
    memset(parents, -1, sizeof(parents));
    std::fill(depth, depth + N, -1);
    depth[0] = 0;
    
    //트리 만들고 parent 초기값 넣기
    initTree(0, adj);

    //parents[K][V] : V노드의 2^k 번째 조상
    //parents[K+1][V] = parents[K][parents[K][V]] : 2^(K+1) == 2*2^K이므로.
    //V의 2^(K+1) 조상은, V의 2^K 조상의 2^K 조상.
    for (int K = 0 ; K < MAX - 1; K++)
    {
        for (int V = 1 ; V < N; V++) // V[0]은 루트.
        {
            if (parents[K][V] != -1) //parents 배열의 해당 자리가 값이 있으면
                parents[K+1][V] = parents[K][parents[K][V]]; //위로 채워나가기;
        }
    }
    int C;
    std::cin >> C;
    
    for (int i = 0; i < C; i++)
    {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;

        if (depth[u] < depth[v])
            std::swap(u,v);
        int diff = depth[u] - depth[v];

        for (int bit = 0; diff; bit++) // 2진법으로 보고 올림. 
        {
            if (diff % 2)
                u = parents[bit][u];
            diff /= 2;
        }
        // 11일경우 1011 2^0, 2^1, 2^3일때, u = parents[bit][u] 실행.
        
        if (u != v)
        {
            for (int height = MAX - 1; height >= 0; height--)
            {
                //가장 위 높이서부터 비교 ... 루트는 당연히 공통조상이므로 if에 안걸리고 어느순간 조상이 달라질때 해당 노드로 갱신.
                if (parents[height][u] != -1 && parents[height][u] != parents[height][v])
                {
                    u = parents[height][u];
                    v = parents[height][v];                
                }
                //u, v 갱신하고 왜 height를 다시 높여서 연산하지 않는가?
                //갱신하고 난 뒤, height를 1 높인다 가정하면, 이미 갱신 전에 if에서 걸리지 않은 공통조상이었기 때문에, 그냥 탐색을 이어나가면 됨!
            }
            u = parents[0][u] ;
        }
        std::cout << u + 1 << "\n"; // +1 처리 안해줘서 틀림.
    }
}

많은 탐색을 2진법의 원리로 휘뚜루마뚜루 처리해버리는게 신기했다. 

 

오늘도 평온한 하루가 되길. 슨민.