문제 소개
이 문제에서는 하나의 이진 트리와 그 트리에 속한 두 개의 노드가 주어집니다. 우리가 해야 할 일은 두 노드 사이의 경로에 놓인 모든 노드 값의 XOR을 계산해 출력하는 것입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
위 트리에서 노드 2와 노드 3 사이 경로의 XOR을 구한다고 가정해 보겠습니다.
- 노드 2에서 노드 3까지의 경로:
2 → 6 → 1 → 3 - 따라서 계산해야 할 식은
2 ^ 6 ^ 1 ^ 3입니다.
접근 방법
두 노드 사이의 경로를 일일이 찾아가는 대신, 루트에서 각 노드까지 이르는 경로의 XOR 누적값을 미리 계산해 두는 방식을 사용합니다. 루트에서 출발해 트리를 깊이 우선으로 순회하면서, 각 노드에 도달할 때까지 누적된 XOR 값을 해시 맵(unordered_map)에 노드 값과 함께 저장합니다.
이렇게 하면 XOR의 다음 성질을 활용할 수 있습니다.
- 같은 값이 두 번 XOR되면 0이 되어 서로 상쇄됩니다. (
a ^ a = 0) - 두 노드의 루트 경로가 공유하는 구간은 양쪽 경로에 모두 포함되므로, 두 누적 XOR 값을 서로 XOR하면 공통 구간이 자동으로 상쇄됩니다.
결국 path[node1] ^ path[node2] 한 번의 연산만으로 답을 구할 수 있습니다. 또한 순회 중 각 단계마다 지금까지의 XOR 결과에 현재 노드 값을 XOR하기만 하므로, 경로 전체를 따로 저장하지 않아도 되어 공간을 절약할 수 있습니다.
시간 복잡도는 트리를 한 번 순회하므로 O(N), 공간 복잡도는 각 노드의 XOR 값을 저장해야 하므로 O(N)입니다.
구현 예제
위 접근 방식을 C++로 구현한 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* getNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void pathStoD(Node* root, unordered_map<int, int>& path, int XOR){
if (!root)
return;
path.insert(make_pair(root->data, XOR ^ root->data));
XOR ^= root->data;
if (root->left)
pathStoD(root->left, path, XOR);
if (root->right)
pathStoD(root->right, path, XOR);
}
int findPathXOR(unordered_map<int, int> path, int node1, int node2){
return path[node1] ^ path[node2];
}
int main(){
struct Node* root = getNode(1);
root->left = getNode(6);
root->left->left = getNode(2);
root->left->right = getNode(4);
root->right = getNode(3);
root->right->left = getNode(7);
root->right->right = getNode(5);
int XOR = 0;
unordered_map<int, int> mp;
int source = 2;
int destination = 3;
pathStoD(root, mp, XOR);
cout<<"The XOR of all node from "<<source<<" to "<<destination<<" of the tree is : ";
cout<<findPathXOR(mp, source, destination);
return 0;
}출력 결과
The XOR of all node from 2 to 3 of the tree is : 7
참고: 최소 공통 조상(LCA)의 상쇄
위 방식에서는 두 노드의 루트 경로에 공통으로 포함되는 최소 공통 조상(LCA) 노드 역시 두 번 XOR되어 결과에서 자연스럽게 제외됩니다. 예제에서 노드 2와 노드 3의 LCA는 루트 노드 1이므로, 프로그램의 출력값 7은 (2 ^ 6) ^ (3), 즉 LCA를 제외한 경로 노드들의 XOR에 해당합니다. 만약 LCA 노드를 결과에 반드시 포함해야 한다면 path[node1] ^ path[node2] ^ LCA값을 추가로 계산해 주면 됩니다.