1248. 공통 조상

1248. 공통 조상

공통 조상 같은 경우에는 LCA라고 하여, 해당하는 노드의 높이를 맞춰준 후에 같이 부모 노드로 거슬러 올라가면서 같은 노

드가 될 때까지 while 문을 이용하여 구할 수 있습니다. 

또한 문제에서 해당하는 조상 노드의 서브 트리의 크기를 구하라고 하였는데, 이는 분할정복을 이용하여 get_size() 함수에

서 자식 노드의 존재 여부를 파악하면서 재귀함수로 구현하였다. 처음에 get_size 에서 ret 값을 0으로 초기화 했었는데, 생각

해보니 그렇게 하면 노드가 자기 자신도 서브 트리의 크기에 포함을 해야하므로 ret 의 초기값을 1로 수정하였다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int get_depth(vector<int>& parent, int v)
{
    int ret = 0;
    int cur = v;
    while (cur != 1)
    {
        ret++;
        cur = parent[cur];
    }
 
    return ret;
}
 
int get_answer(vector<int>& parent, int n1, int n1_d, int n2, int n2_d)
{
    if (n1_d > n2_d)
    {
        while (n1_d != n2_d)
        {
            n1_d--;
            n1 = parent[n1];
        }
    }
 
    if (n1_d < n2_d)
    {
        while (n1_d != n2_d)
        {
            n2_d--;
            n2 = parent[n2];
        }
    }
 
    while (n1 != n2)
    {
        n1 = parent[n1];
        n2 = parent[n2];
    }
 
 
    return n1;
}
 
int get_size(vector<vector<int>>& child, int cur)
{
    int ret = 1;
 
    if (child[cur].size() == 0)
        return 1;
 
    for (int i = 0; i < child[cur].size(); i++)
    {
        ret += get_size(child, child[cur][i]);
    }
 
    return ret;
}
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int V, E, node1, node2;
        int node1_depth, node2_depth;
        cin >> V >> E >> node1 >> node2;
 
        vector<int> parent(V + 1);
        vector<vector<int>> child(V + 1);
 
        for (int i = 0; i < E; i++)
        {
            int from, to;
            cin >> from >> to;
            parent[to] = from;
            child[from].push_back(to);
        }
 
        node1_depth = get_depth(parent, node1);
        node2_depth = get_depth(parent, node2);
 
        int ancess = get_answer(parent, node1, node1_depth, node2, node2_depth);
        int size = get_size(child, ancess);
 
        cout << "#" << t << " " << ancess << " " << size << endl;
 
    }
 
    return 0;
}