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

문제 소개

이 글에서는 트리에서 두 노드 사이의 조상-자손 관계를 판별하는 쿼리 문제를 다룹니다.

루트가 있는 트리(rooted tree)와 Q개의 쿼리가 주어지며, 각 쿼리에 담긴 두 노드 중 한 노드가 다른 노드의 조상인지 아닌지를 확인하는 것이 과제입니다.

접근 방법: DFS 진입·탈출 시간 활용

쿼리마다 매번 부모를 거슬러 올라가며 조상 여부를 확인하면 매우 비효율적입니다. 대신 DFS(깊이 우선 탐색)를 딱 한 번 수행하면서 각 노드의 진입 시간(timeIn)과 탈출 시간(timeOut)을 기록해 두면, 이후 모든 쿼리를 상수 시간 O(1)에 처리할 수 있습니다.

• timeIn[u] : DFS가 노드 u에 처음 방문한 순번
• timeOut[u] : 노드 u의 모든 자손 탐색을 끝내고 떠나는 순번

노드 u가 노드 v의 조상일 필요충분조건은 다음과 같습니다.

timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u]

조상 노드는 항상 자손 노드보다 먼저 방문되고, 모든 자손의 탐색이 완료된 후에야 떠나기 때문입니다. 이를 흔히 오일러 투어(Euler Tour) 기법이라고 부릅니다.

C++ 구현 코드

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

// DFS를 이용해 주어진 노드들의 관계 파악
void performingDFS(vector<int> g[], int u, int parent,
                   int timeIn[], int timeOut[], int& count) {
    // 노드에 진입할 때 timeIn 기록
    timeIn[u] = count++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v != parent)
            performingDFS(g, v, u, timeIn, timeOut, count);
    }
    // 노드를 떠날 때 timeOut 기록
    timeOut[u] = count++;
}

void processingEdges(int edges[][2], int V, int timeIn[], int timeOut[]) {
    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 count = 0;
    // 0번 노드를 루트로 하여 DFS 시작
    performingDFS(g, 0, -1, timeIn, timeOut, count);
}

// 한 노드가 다른 노드의 조상인지 검사
string whetherAncestor(int u, int v, int timeIn[], int timeOut[]) {
    bool b = (timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u]);
    return (b ? "yes" : "no");
}

int main() {
    int edges[][2] = {
        { 0, 1 },
        { 0, 2 },
        { 1, 3 },
        { 1, 4 },
        { 2, 5 },
    };
    int E = sizeof(edges) / sizeof(edges[0]);
    int V = E + 1;
    int timeIn[V], timeOut[V];
    processingEdges(edges, V, timeIn, timeOut);

    int u = 1;
    int v = 5;
    cout << whetherAncestor(u, v, timeIn, timeOut) << endl;
    return 0;
}

실행 결과

no

동작 원리 살펴보기

예제 트리는 0번 노드를 루트로 하며, 0의 자식은 1과 2, 1의 자식은 3과 4, 2의 자식은 5입니다. 쿼리에서는 노드 1이 노드 5의 조상인지를 묻습니다. 그러나 노드 5는 노드 2의 자식이므로 노드 1의 자손이 아니며, 따라서 결과는 "no"가 출력됩니다.

시간 복잡도

• 전처리(DFS 수행) : O(V + E)
• 쿼리당 조상 판별 : O(1)

전처리를 한 번만 해두면 어떤 두 노드에 대해서도 즉시 조상 여부를 알 수 있기 때문에, 쿼리 개수가 많은 상황에서 특히 유용하게 활용할 수 있는 기법입니다.