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

문제링크 : https://www.acmicpc.net/problem/3584

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N, A, B, X, Y;
int parent[10001];
int visited[10001];

int dfs(int n)
{
    if(visited[n]) return n; //방문체크
    return dfs(parent[n]); //부모찾기
}

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

    cin >> T;
    while(T--)
    {
        memset(parent, 0 , sizeof(parent)); //테스트케이스마다 초기화
        memset(visited, 0, sizeof(visited));
        cin >> N;
        for(int i=0; i<N-1; i++)
        {
            cin >> A >> B;
            parent[B]=A; //B의 부모는 A
        }
        cin >> X >> Y;
        while(X) //X기준 조상 노드들 방문 처리
        {
            visited[X]=1;
            X=parent[X];
        }
        cout << dfs(Y) << "\n"; //A 부모 탐색 중 이미 방문된 값 있으면 해당 값 출력
    }
}

이번 문제로 최소 공통 조상 문제에 대해 처음 접하게되었다.

줄여서 LCA라고 알고리즘이 따로 있는 듯 했지만 해당 문제는 LCA 알고리즘까지는 필요없이 다소 간단하게 풀 수 있는 것 같았다.

 

먼저 공통 조상을 구할 첫 번째 노드인 X를 기준으로 X 위로 조상 노드들을 모두 방문처리 시켜준다.

그리고 두 번째 노드인 Y를 기준으로 조상 노드들을 찾기 시작하는데 이미 X를 기준으로 탐색해주면서 방문처리를 했던 값이라면 해당 값을 반환시켜준다.

지금 방문하는데 전에 이미 방문했다는 것은 공통되는 조상 노드라는 것을 의미하기 때문이다.

 

X : 16
16 -> 10 -> 4 -> 8

Y : 7
7 -> 6 -> 4 -> 8

가장 먼저 겹치는 조상 노드 : 4