[백준] 3584 가장 가까운 공통 조상 (C++)

문제

3584번: 가장 가까운 공통 조상 (acmicpc.net)

3584번: 가장 가까운 공통 조상

 

풀이

두 노드의 공통 조상을 찾는다면 부모 노드로 하나씩 거슬러 올라가며 부모가 같은 노드인지 확인하는 방법이 가장 간단합니다.

우선 부모가 같기 위해서는 루트로부터의 깊이가 같아야 합니다. 그렇기 때문에 주어진 두 노드의 깊이가 다르다면 깊이를 맞춰주는것이 우선입니다.

 

두 노드의 깊이가 같다면 동시에 하나씩 부모로 거슬러 올라가며 비교를 합니다. 두 노드가 같다면 그 때의 노드 번호를 출력합니다.

 

 

앞서 말한대로 문제를 해결하기 위해 노드가 가져야할 정보는 깊이, 부모노드, 자식노드 입니다.

struct Node
{
    int depth;
    int parent;
    vector<int> childs;
};

 

 

우선 루트노드가 무엇인지부터 확인해야 합니다. 어떤 노드의 자식노드들은 루트가 될 수 없습니다. 자식으로 입력된 노드들을 하나씩 지우다보면 남은 하나의 노드가 루트노드가 됩니다.

        for(int i=0; i<n-1; ++i)
        {
            int parent, child;
            cin >> parent >> child;
            tree[parent].childs.push_back(child);
            tree[child].parent = parent;
            isRoot[child] = false;
        }

 

 

이제 dfs 탐색을 통해 각 노드들의 깊이를 계산할 수 있습니다.

void dfs(int cur, int depth)
{
    tree[cur].depth = depth;
    for (int next : tree[cur].childs)
    {
        dfs(next, depth+1);
    }
}

int main()
{
// ...
        for (int i=1; i<n+1; ++i)
        {
            if (isRoot[i])
            {
                dfs(i, 0);
            }
        }
// ...

 

 

노드들의 모든 정보가 준비되었으니 최소 공통 조상 노드를 찾아봅시다.

위에서 언급한대로 깊이를 우선 맞춰주고 하나씩 부모노드로 거슬러 올라가며 비교합니다.

int findLCA(int a, int b)
{
    if (a == b)
    {
        return a;
    }

    if (tree[a].depth < tree[b].depth)
    {
        b = tree[b].parent;
    }
    else if (tree[a].depth > tree[b].depth)
    {
        a = tree[a].parent;
    }
    else
    {
        a = tree[a].parent;
        b = tree[b].parent;
    }
    return findLCA(a, b);
}

 

저는 재귀함수로 구현했지만 사실 LCA 를 반복문으로 구현하는 방법이 더 빠를 것이고,
부모를 찾기 위해 하나씩 거슬러 올라가기 보다는 희소 배열 알고리즘을 활용한다면 더욱 빠른 시간안에 문제를 해결할 수 있을 것입니다.

 

나중에 이에 대한 내용은 따로 정리하겠습니다.

 

관련 문제로는 11438번: LCA 2 (acmicpc.net) 문제가 있습니다.

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
    int depth;
    int parent;
    vector<int> childs;
};

int testcase;
int n;
vector<Node> tree;
vector<bool> isRoot;

void dfs(int cur, int depth)
{
    tree[cur].depth = depth;
    for (int next : tree[cur].childs)
    {
        dfs(next, depth+1);
    }
}

int findLCA(int a, int b)
{
    if (a == b)
    {
        return a;
    }

    if (tree[a].depth < tree[b].depth)
    {
        b = tree[b].parent;
    }
    else if (tree[a].depth > tree[b].depth)
    {
        a = tree[a].parent;
    }
    else
    {
        a = tree[a].parent;
        b = tree[b].parent;
    }
    return findLCA(a, b);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> testcase;
    while (testcase--)
    {
        cin >> n;
        tree.resize(n+1);
        isRoot.resize(n+1, true);
        for(int i=0; i<n-1; ++i)
        {
            int parent, child;
            cin >> parent >> child;
            tree[parent].childs.push_back(child);
            tree[child].parent = parent;
            isRoot[child] = false;
        }

        for (int i=1; i<n+1; ++i)
        {
            if (isRoot[i])
            {
                dfs(i, 0);
            }
        }
        
        int a, b;
        cin >> a >> b;
        cout << findLCA(a, b) << "\n";

        tree.clear();
        isRoot.clear();
    }
    return 0;
}