문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

내 풀이

트리에서 최소 공통 조상(이하 LCA)를 찾는 방법을 몰라서 여러 블로그에서 찾아서 풀었다.

이 문제는 입력에서 트리의 루트를 알려주지 않기 때문에 따로 루트를 찾는 과정을 넣어야 했고, 입력이 들어올 때 부모 자식 관계가 나오기 때문에 단반향으로 그래프를 입력 받고, 찾아낸 루트부터 DFS를 돌려 트리의 정보를 업데이트 했다.(set_tree에서 parent와 level)

동일한 깊이에서 시작해 부모노드로 올라가면서 같은 부모가 나올 때 까지 반복하는것으로 LCA를 구했다.

시간복잡도는 $O(depth)$ 이고 최대 깊이는 10000 이기 때문에 시간제한에도 걸리지 않는다.

배운점

블로그에서 LCA코드를 가져와서 조금 아쉬웠다. 하지만 루트를 알지 못하는 상태에서 트리의 루트를 찾는 방법을 배웠다. 특정 노드로 루트를 찾는 함수를 시작해 해당 노드를 자식으로 갖는 부모를 찾고, 그 부모로 다시 루트를 찾는 함수를 재귀적으로 시행하는것으로 루트를 찾았다.

소스코드

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

int test_case, node_num, node1, node2;
vector<vector<int>> grape(10005);
vector<int> parent(10005, 0), level(10005, 0);

int lca(int a, int b){
    if(level[a] < level[b]) return lca(b, a);

    while(level[a] > level[b]){
        a = parent[a];
    }

    while(a != b){
        a = parent[a];
        b = parent[b];
    }
    return a;
}

void set_tree(int node, int pnode){
    parent[node] = pnode;
    level[node] = level[pnode] + 1;
    for(int i = 0; i < grape[node].size(); i++){
        int child = grape[node][i];
        if(child == pnode) continue;
        set_tree(child, node);
    }
}

int find_root(int temp){
    for(int i = 1; i <= node_num; i++){
        for(int j = 0; j < grape[i].size(); j++){
            if(grape[i][j] == temp){
                return find_root(i);
            }
        }
    }
    return temp;
}

void init(){
    cin >> node_num;
    int parent_node, child_node;
    for(int i = 0; i < node_num-1; i++){
        cin >> parent_node >> child_node;
        grape[parent_node].push_back(child_node);
    }
    cin >> node1 >> node2;
}

int main(){
    ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
    cin >> test_case;
    while(test_case--){
        vector<vector<int>> temp(10005, vector<int>());
        vector<int> temp_parent_level(10005, 0);
        grape = temp;
        parent = level = temp_parent_level;
        init();
        set_tree(find_root(1), 0);
        cout << lca(node1, node2) << "\n";
    }
    return 0;
}