11437-LCA

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

11437번: LCA

본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다.

 

LCA 는 Lowest Common Ancestor 의 축약어로써 트리에서 특정 두 노드의 공통 조상(Ancestor) 노드 중에서 Depth 가 가장 큰 노드를 찾는 문제입니다.

 

이와 관련하여 정리가 잘된 글이 있어 링크를 첨부합니다.

https://jason9319.tistory.com/90

 

저는 아래와 같이 알고리즘을 구현하였습니다.

 

1. 노드간의 연결 관계를 입력받고 이로부터 트리를 구성(DFS)

 

2. 각 노드별로 Depth 와 Ancestor 노드 정보(1번째, 2번째, 4번째, ... , 2^j 번째 Ancestor)를 저장

 

각 노드별로 단순히 1번째 Parent 만 저장하는 게 아니고 2번째, 4번째, ..., 2^j 번째 Ancestor 노드의 정보까지 저장하는 게 알고리즘의 핵심입니다.

 

이때, i번 노드의 2^j 번째 Ancestor 노드를 탐색하는 게 굉장히 어려워 보입니다. 그런데, Dynamic Programming 기법을 사용해서 쉽게 구할 수 있습니다.

 

"i 번 노드의 2^j 번째 Ancestor 노드"는 "i번 노드의 2^(j-1) 번째 Ancestor 노드의  2^(j-1) 번째 Ancestor 노드"입니다.

 

이는 Depth 7 에 해당하는 트리를 직접 그려보시고 Leaf 노드로 부터 Root 노드까지 Ancestor 노드간에 관계를 직접 확인해보시면 이해가 되실겁니다.

3. LCA 를 찾고자 하는 두 노드의 Depth 를 동일하게 맞춤. 이때, 두 노드 중 Depth 의 크기가 더 큰 노드가 Depth 의 크기가 더 낮은 노드와 동일해지도록 Bottom-up 방식으로 이동

 

두 노드의 Depth 차이가 크더라도 우리는 2. 단계에서 저장한 Ancestor 정보를 이용하여 최대 2^j 만큼 Depth 차이를 줄여나갈 수 있습니다. 해당 과정은 O(log N) 의 복잡도를 가집니다.

 

4. Depth 가  K 인 두 노드로 부터 Ancestor 노드로 이동하며 LCA 를 탐색

 

LCA 의 Depth 와 K  와의 차이가 크더라도 우리는 2. 단계에서 저장한 Ancestor 정보를 이용하여 최대 2^j 만큼 Depth 차이를 줄여나갈 수 있습니다.

 

방법은 두 노드로 부터 우선 2^j 번째 Ancestor 노드를 확인해보고 두 Ancestor 노드가 같지 않으면 두 노드를 2^j 번째 Ancestor 노드로 변경합니다. 만약 두 Ancestor 노드가 같다면 2^(j-1) 번째 Ancestor 노드를 확인해본다음 위 과정을 두 Ancestor 노드가 서로 다를때까지 반복합니다.

 

위 과정을 통해 변경된 두 노드의 Parent 노드가 LCA 가 됩니다.

 

코드

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int N; //(2<= N <= 50000), 트리를 이루는 정점(=Node)의 개수
int M; //(1<= M <= 10000), 두 노드의 쌍
int max_ancestor_num_per_node;

vector<vector<int>> connection_descriptor; // 노드간 연결 표현

struct tree{
    vector<vector<int>> ancestor; // ancestor[i][j] = i 번 노드의 2^j 번째 Ancestor 노드 번호
    vector<int> depth; // depth[i] = i 번 노드의 Depth
};

tree t;

void define_tree(int node, int depth)
{
    for(int connected_node:connection_descriptor[node])
    {
        if(t.ancestor[connected_node][0] == -1) //"Node" 와 연결된 다른 Node 의 부모가 정의되어 있지 않은 경우
        {
            // 연결된 다른 Node 의 부모를 "Node" 로 정의
            // 연결된 다른 Node 의 Depth 를 "Node" 의 Depth 보다 1 더 높임

            t.ancestor[connected_node][0] = node;
            t.depth[connected_node] = depth + 1;
            define_tree(connected_node, depth + 1);
        }
    }
}

void define_ancestors()// 각 노드별로 조상 탐색
{
    int max_ancestor_num = t.ancestor[0].size();
    for(int i = 1; i < max_ancestor_num; i++)
        for(int j = 1; j <= N; j++)
        {
            //j 번 노드의 2^i 번째 부모노드는 j번째 노드의 2^(i-1) 번째 Ancestor의 2^(i-1) 번째 Ancestor
            t.ancestor[j][i] = t.ancestor[t.ancestor[j][i-1]][i-1];
        }
}

int lca(int node1, int node2)
{
    if(t.depth[node1] < t.depth[node2]) 
        swap(node1, node2);
    
    for (int i = 16; i >= 0; i--) 
    {
        if(t.depth[node1] - t.depth[node2] >= (1 << i))
            node1 = t.ancestor[node1][i];
    }

    if(node1 == node2) return node1;

    for (int i = 16; i >= 0; i--)
    {
        if(t.ancestor[node1][i] != t.ancestor[node2][i])
        {
            node1 = t.ancestor[node1][i];
            node2 = t.ancestor[node2][i];
        }
    }

    return t.ancestor[node1][0];
}


int main()
{
    ios::sync_with_stdio(false);    
    cin.tie(NULL);
    cin >> N;

    connection_descriptor.resize(N + 1);

    t.ancestor = vector<vector<int>>(N + 1, vector<int>(17, -1));
    t.depth = vector<int>(N + 1);

    t.ancestor[1][0] = 1; // Root 노드의 부모 노드를 자기 자신으로 정의
    t.depth[1] = 0; // Root 노드의 Depth 를 0 으로 정의

    // 노드간 연결 정의
    for(int i = 0; i < N - 1; i++)
    {
        int node1;
        int node2;
        cin >> node1 >> node2;

        connection_descriptor[node1].push_back(node2);
        connection_descriptor[node2].push_back(node1);
    }

    define_tree(1, 0);
    define_ancestors();

    cin >> M;

    for(int i = 0; i < M; i++)
    {
        int node1;
        int node2;
        cin >> node1 >> node2;

        cout << lca(node1, node2) << '\n';
    }

    return 0;
}