[C++ 백준 풀이] 3584번 : 가장 가까운 공통 조상 (Easy LCA)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3584번 : '가장 가까운 공통 조상' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold IV에 해당하며, 문제를 풀이하기 위해 트리에 대한 기본 지식이 필요합니다.

 

지난 포스트에서 LCA에서 Parent 배열에 2^k번째 부모 노드들을 저장하는 방법을 통해 10만 단위의 N에 대해서도 빠른 풀이를 하는 방법을 다루어보았습니다.

 

그러나 작은 범위의 트리에 대해서 LCA를 더 간단하게 구현하는 방법은 뭐가 있을까요? (순서가 반대로 된 것 같지만 이번 포스트에서는 더 쉬운 LCA 문제는 어떻게 구현하면 간단할지 알아보도록 하겠습니다.)

 

 

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

 

문제에서 가장 가까운 공통 조상의 정의에 대해 다루고, 루트가 주어지지 않은 (하지만 존재는 하는) 트리를 입력으로 주고 두 노드 사이의 가장 가까운 공통 조상을 구하라고 하였습니다.

 

이전에 해결한 문제는 1번 노드가 반드시 루트 노드로 지정이 되어 있었지만, 여기서는 루트 노드가 따로 지정이 되지 않습니다.

 

모든 노드들의 부모를 찾아서 연결하고, 두 노드의 최소 공통 조상을 찾아봅시다.

 

 

#include <cstdio>
#define MAX 10001
using namespace std;
 
int Parent[MAX];
bool Visit[MAX];
 
int main() {
    int T, N, A, B, U, V;
    scanf("%d", &T);
    for(int t=0; t<T; t++) {
        scanf("%d", &N);
        for(int i=1; i<=N; i++) {
            Parent[i] = i;
            Visit[i] = false;
        }
        for(int i=0; i<N-1; i++) {
            scanf("%d %d", &A, &B);
            Parent[B] = A;
        }
        scanf("%d %d", &U, &V);
        Visit[U] = true;
        while(Parent[U] != U) {
            U = Parent[U];
            Visit[U] = true;
        }
        while(1) {
            if(Visit[V] == true || V == Parent[V]) break;
            else V = Parent[V];
        }
        printf("%d\n", V);
    }
}
 

 

풀이는 생각보다 간단한데, 이는 시간 초과의 제한을 받지 않고 상식적인 선에서 풀이가 가능하기 때문입니다.

우선 모든 노드들을 입력받고 노드들의 부모를 자기 자신으로, visit을 0으로 초기화 해줍니다. (사실 노드들의 부모를 자기 자신으로 초기화 하는 것은 굳이 하지 않아도 풀이할 수는 있습니다.)

 

그 다음 모든 부모 - 자식 노드를 입력받아 연결을 수행해줍니다.

이 연결은 Parent 배열에 저장하여 Parent[B] = A는 B의 부모 노드가 A라는 의미를 내포합니다.

그 다음 최소 공통 조상을 찾을 두 노드를 입력받아, 한 노드는 최상위 노드(U = Parent[U])에 도달할 때까지 거슬러 올라가며 모두 check 해줍니다.

그리고 이 과정을 V에 대해서도 마찬가지로 하되, 처음으로 visit에 check 되어 있는 노드를 만나면 그 노드가 최소 공통 조상이 되게 됩니다.

 

+ 문제에서는 반드시 LCA가 존재하는 경우만 테스트케이스로 주어지지만, 만약 그렇지 않은 경우도 주어진다면 위의 코드와 같이 V == Parent[V]인 경우도 break의 조건으로 달아야 합니다.

 

 

 

풀이 코드를 제출해보면 짧은 시간에 모든 테스트케이스를 통과하였음을 확인할 수 있습니다.