C++로 트리에서 조상-후손 관계 쿼리 처리하기

이 문제에서는 N개의 정점으로 이루어진 트리와, 두 개의 값 i와 j로 구성된 Q개의 쿼리가 주어집니다. 우리가 작성해야 하는 프로그램은 트리 안에서 두 노드 사이의 조상-후손(ancestor-descendant) 관계를 판별하는 쿼리를 처리하는 것입니다.

즉, 각 쿼리마다 노드 i가 노드 j의 조상인지 여부를 확인해야 합니다.

문제 이해를 돕는 예시

C++로 트리에서 조상-후손 관계 쿼리 처리하기 – 오일러 경로 기법 활용

입력

Q = 2, query[][] = {{3, 5}, {1, 6}}

출력

No Yes

설명

i = 3, j = 5 : 노드 3은 노드 5의 조상이 아니므로 NO를 출력합니다.
i = 1, j = 6 : 노드 1은 노드 6의 조상이므로 YES를 출력합니다.

해결 접근 방법

가장 직관적인 방법은 DFS(깊이 우선 탐색)로 i번 노드에서 출발해 모든 후손을 순회하면서 j번 노드가 등장하는지 확인하는 것입니다. 하지만 쿼리 개수가 많아지면 매번 트리를 다시 순회해야 하므로 비효율적입니다.

더 효율적인 방법은 오일러 경로(Euler Tour) 기법을 활용하는 것입니다. DFS를 수행하면서 각 노드에 대해 진입 시점(entTime)과 종료 시점(exitTime)을 기록해 두면, 다음과 같은 성질이 성립합니다.

노드 u가 노드 v의 조상일 필요충분조건: entTime[u] ≤ entTime[v] 그리고 exitTime[u] ≥ exitTime[v]

쉽게 말해, u의 방문 구간이 v의 방문 구간을 완전히 감싸고 있다면 u는 v의 조상입니다. 전처리는 O(N)에 한 번만 수행되고, 이후 각 쿼리는 O(1)에 답변할 수 있으므로 전체 시간 복잡도는 O(N + Q)가 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void depthFirstSearch(vector<int> g[], int u, int parent, int entTime[], int exitTime[], int& cnt){
    entTime[u] = cnt++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v != parent) depthFirstSearch(g, v, u, entTime, exitTime, cnt);
    }
    exitTime[u] = cnt++;
}

void calcTimeInAndOut(int edges[][2], int V, int entTime[], int exitTime[]){
    vector<int> g[V];
    for (int i = 0; i < V - 1; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int cnt = 0;
    depthFirstSearch(g, 0, -1, entTime, exitTime, cnt);
}

int main(){
    int edges[][2] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 1, 4 }, { 4, 5 }, { 5, 6 }, { 5, 7 }};
    int E = sizeof(edges) / sizeof(edges[0]);
    int V = E + 1;
    int Q = 2;
    int query[Q][2] = {{3, 5}, {1, 6}};
    int entTime[V], exitTime[V];
    calcTimeInAndOut(edges, V, entTime, exitTime);

    for (int i = 0; i < Q; i++){
        cout << "For query " << (i+1) << " : ";
        if (entTime[query[i][0]] <= entTime[query[i][1]] && exitTime[query[i][0]] >= exitTime[query[i][1]])
            cout << "is Ancestor\n";
        else
            cout << "is not Ancestor\n";
    }
    return 0;
}

실행 결과

For query 1 : is not Ancestor
For query 2 : is Ancestor

정리

DFS 순회 과정에서 각 노드의 진입 시간과 종료 시간을 미리 계산해 두면, 조상-후손 관계를 묻는 쿼리를 추가적인 트리 순회 없이 상수 시간에 처리할 수 있습니다. 이 오일러 경로 기법은 LCA(최소 공통 조상) 같은 다른 트리 쿼리 문제에도 널리 응용되는 핵심 기술이므로, 함께 익혀 두면 큰 도움이 됩니다.