C++로 트리에서 주어진 노드의 서브트리 전체 XOR 값 구하기

문제 개요

이 문제에서는 n개의 노드로 이루어진 트리가 주어지고, 여러 개의 쿼리가 트리의 특정 노드를 가리킵니다. 우리의 과제는 주어진 노드를 루트로 하는 서브트리에 포함된 모든 노드 값의 XOR을 출력하는 것입니다.

예시를 통해 문제를 살펴보겠습니다.

쿼리 − {1, 6, 5}

출력 −

0
0
5

설명 −

1^6^3^2^4^7^5 = 0
6^2^4 = 0
5 = 5

접근 방법

이 문제를 효율적으로 해결하려면 트리를 딱 한 번만 순회하면서 각 노드를 루트로 하는 서브트리의 XOR 값을 미리 계산해 저장해 두는 것이 핵심입니다. 리프 노드부터 차례대로 자식 노드들의 서브트리 XOR 값을 현재 노드의 값과 배타적 OR(XOR) 연산으로 결합하면, 상위 노드의 서브트리 XOR도 자연스럽게 구할 수 있습니다. 결과를 배열에 저장해 두면 이후 어떤 쿼리가 들어와도 트리를 다시 순회할 필요 없이 즉시 답을 얻을 수 있어 실행 시간을 크게 절약할 수 있습니다.

XOR 연산은 교환 법칙과 결합 법칙이 성립하기 때문에 서브트리 내 노드들을 어떤 순서로 XOR하더라도 결과는 동일합니다. 또한 같은 값을 두 번 XOR하면 0이 되는 성질(x ^ x = 0) 덕분에 이러한 누적 방식이 정확하게 동작합니다.

알고리즘 단계

DFS(깊이 우선 탐색)를 이용해 루트 노드부터 트리를 순회합니다.
각 노드에서는 자신의 값으로 초기화한 뒤, 부모가 아닌 인접 노드(자식)들의 서브트리 XOR 값을 현재 값과 XOR 연산합니다.
계산이 끝난 노드의 XOR 값을 xorValues 배열에 저장하고, 그 값을 호출자에게 반환합니다.
쿼리가 들어오면 xorValues 배열에서 해당 노드의 값을 그대로 반환합니다.

C++ 구현

다음 프로그램은 위에서 설명한 접근 방식을 C++로 구현한 것입니다.

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

vector<vector<int>> graph;
vector<int> values, xorValues;

// 각 노드를 루트로 하는 서브트리의 XOR 값을 재귀적으로 계산
int computeXorValues(int i, int prev){
    int x = values[i];
    for (int j = 0; j < graph[i].size(); j++)
        if (graph[i][j] != prev) {
            x ^= computeXorValues(graph[i][j], i);
        }
    xorValues[i] = x;
    return x;
}

// 미리 계산된 값을 이용해 쿼리를 O(1)에 처리
int solveQuery(int u){
    return xorValues[u];
}

int main(){
    int n = 7;
    graph.resize(n);
    xorValues.resize(n);

    // 트리 구성 (인접 리스트)
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(5);
    graph[2].push_back(6);

    // 각 노드의 값
    values.push_back(1);
    values.push_back(2);
    values.push_back(3);
    values.push_back(4);
    values.push_back(5);
    values.push_back(6);
    values.push_back(7);

    // 루트(0)부터 DFS로 서브트리 XOR 사전 계산
    computeXorValues(0, -1);

    int queries[] = { 0, 2, 4, 6 };
    int q = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < q; i++)
        cout << "Solution for query " << (i+1) << ": " << solveQuery(queries[i]) << endl;
    return 0;
}

실행 결과

Solution for query 1: 0
Solution for query 2: 2
Solution for query 3: 5
Solution for query 4: 7

코드 설명

graph: 트리를 인접 리스트 형태로 표현합니다.
values: 각 노드에 저장된 값을 담습니다.
xorValues: 각 노드를 루트로 하는 서브트리의 XOR 값을 저장합니다.
computeXorValues(): 재귀적으로 서브트리를 순회하며 XOR 값을 계산하고 저장합니다.
solveQuery(): 미리 계산된 값을 반환해 각 쿼리를 O(1) 시간에 처리합니다.

복잡도 분석

시간 복잡도: 전처리(DFS)에 O(N), 각 쿼리 처리에 O(1)이 소요되므로 전체 시간 복잡도는 O(N + Q)입니다. 여기서 N은 노드 수, Q는 쿼리 수입니다.

공간 복잡도: 인접 리스트와 XOR 값 저장 배열을 위해 O(N)의 추가 공간이 필요합니다.