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

문제

접근 방법

깊이를 맞추어주고 같이 올라가다보면 같은 값이 나오는 구간이 있다. 그것이 최소 공통 조상이다.

코드

#include <iostream>
#include <cstring>
using namespace std;
int parent[10001];
int getDepth(int cur)
{
    int cnt = 0;
    while (cur != 0)
    {
        cur = parent[cur];
        ++cnt;
    }
    return cnt;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        memset(parent, 0, sizeof(parent));
        int N, p, c;
        cin >> N;
        while (N-- > 1)
        {
            cin >> p >> c;
            parent[c] = p;
        }
        cin >> p >> c;
        int n1 = getDepth(p), n2 = getDepth(c);
        while (n1 != n2)
        {
            if (n1 > n2)
            {
                p = parent[p];
                --n1;
            }
            else
            {
                c = parent[c];
                --n2;
            }
        }
        while (p != c)
        {
            c = parent[c];
            p = parent[p];
        }
        cout << p << "\n";
    }
}

풀이

더 깊은 곳을 찾아낸 뒤 깊이를 얕은 곳과 맞추어준다. 그 후 같이 올라가다 보면 값이 같아지는데 그것은 조상이 같다는 의미이다.
다른 풀이가 있나 해서 찾아보니 한쪽에서 끝까지 거슬러 올라간 뒤 다른 쪽에서 올라가면서 이미 지나간 곳인지 확인하는 방식이 있었다. (bool 배열을 활용한 방식) 더 간단한 방법인 것 같다고 생각한다.