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

04 Dec 2023 in Study on Coding Test

LCA, 최소 공통 조상을 찾는 문제

정답제출코드

#include <iostream>

#define MAX 10001

using namespace std;

int N;
int Parent[MAX];
bool visited[MAX];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    for (int tc = 0; tc < T; ++tc)
    {
        cin >> N;

        for (int i = 1; i <= N; ++i)
        {
            Parent[i] = i;
            visited[i] = false;
        }
        
        for (int i = 0; i < N - 1; ++i)
        {
            int a, b;
            cin >> a >> b;
            Parent[b] = a;
        }

        int u, v;
        cin >> u >> v;
        visited[u] = true;

		while (u != Parent[u])
		{
			u = Parent[u];
			visited[u] = true;
		}
		while (true)
		{
			if (visited[v])
			{
				cout << v << '\n';
				break;
			}
			v = Parent[v];
		}
    }

    return 0;
}

LCA의 기초 문제이다.

이전에 풀었던 방법이 생각이 난다.

부모 노드를 거슬러 올라가면서 DFS를 진행하면서 찾는 다른 노드가 있는지 탐색을 했는데

DFS를 돌리는 수가 늘어나면 결국에 시간복잡도는 정말 최악의 경우 O(N^3)이 되기에

노드가 10000개인 편향트리를 탐색하게 된다면 이건 정말로 타임오버감이다.

그래서 나온 방법이 위의 방법으로,

한쪽에서 부모 노드를 거슬러 올라가면서 방문처리를 해주고

다른쪽에서 부모 노드를 거슬러 올라가면서 방문 처리한 노드를 만나면

그 노드가 바로 교차점, 즉 최소 공통 조상인 것이다.

이렇게 하면 O(2N)으로 줄일 수 있다.