문제 소개
노드 값이 1부터 9 사이의 숫자로 이루어진 이진 트리가 있다고 가정해 보겠습니다. 어떤 경로에 포함된 노드 값들을 재배열했을 때 적어도 하나의 순열이 회문(palindrome)이 된다면, 그 경로를 의사 회문(pseudo-palindromic) 경로라고 부릅니다. 우리가 구해야 할 것은 루트 노드에서 리프(잎) 노드까지 이어지는 모든 경로 중 의사 회문 경로의 개수입니다.
예시로 이해하기
예를 들어 아래와 같은 이진 트리가 입력으로 주어졌다고 합시다.
이때 기대되는 출력은 2입니다. 그 이유를 살펴보면, 루트에서 리프 노드로 가는 경로는 총 세 개입니다.
- 빨간색 경로: [2, 3, 3]
- 초록색 경로: [2, 1, 1]
- 나머지 경로: [2, 3, 1]
세 경로 중 빨간색 경로 [2,3,3]은 [3,2,3]으로 재배열할 수 있고, 초록색 경로 [2,1,1]은 [1,2,1]로 재배열할 수 있으므로 두 경로가 의사 회문 경로에 해당합니다. 반면 [2,3,1]은 어떻게 재배열하더라도 회문을 만들 수 없기 때문에 제외됩니다.
해결 접근 방법
핵심 아이디어는 간단합니다. 어떤 수열이 회문으로 재배열 가능하려면, 홀수 번 등장하는 숫자의 개수가 최대 1개여야 합니다. 이 성질을 이용해 깊이 우선 탐색(DFS)으로 각 경로의 숫자 개수를 추적하며 문제를 해결할 수 있습니다.
알고리즘 단계
- 배열 v를 인자로 받는 함수 ok()를 정의합니다.
- odd := 0 으로 초기화합니다.
- v의 각 원소 it에 대해 odd := odd + (it AND 1) 을 수행합니다. (홀수 개수 카운팅)
- odd가 0 또는 1이면 true를, 그렇지 않으면 false를 반환합니다.
- node와 배열 v를 인자로 받는 함수 dfs()를 정의합니다.
- node가 null이면 그대로 반환합니다.
- v[node의 값]을 1 증가시킵니다.
- node의 왼쪽과 오른쪽 자식이 모두 null이라면(리프 노드):
- ok(v)가 true이면 ret을 1 증가시킵니다.
- v[node의 값]을 다시 1 감소시키고(백트래킹) 반환합니다.
- 그렇지 않으면 dfs(node의 왼쪽 자식, v)와 dfs(node의 오른쪽 자식, v)를 재귀 호출합니다.
- 재귀가 끝나면 v[node의 값]을 1 감소시켜 상태를 복원합니다.
메인 메서드 처리 흐름
- ret := 0 으로 초기화합니다.
- 크기가 10인 배열 cnt를 선언합니다. (숫자 1~9의 등장 횟수 저장)
- dfs(root, cnt)를 호출합니다.
- ret 값을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 명확하게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}
else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}
else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
int ret;
bool ok(vector <int>& v){
int odd = 0;
for (auto& it : v) {
odd += it & 1;
}
return odd == 0 || odd == 1;
}
void dfs(TreeNode* node, vector <int>& v){
if (!node)
return;
v[node->val]++;
if (!node->left && !node->right) {
if (ok(v))
ret++;
v[node->val]--;
return;
}
dfs(node->left, v);
dfs(node->right, v);
v[node->val]--;
}
int pseudoPalindromicPaths (TreeNode* root) {
ret = 0;
vector<int> cnt(10);
dfs(root, cnt);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,3,1,3,1,NULL,1};
TreeNode *root = make_tree(v);
cout << (ob.pseudoPalindromicPaths(root));
}입력
{2,3,1,3,1,NULL,1}출력
2
마무리
이 문제는 DFS와 백트래킹, 그리고 회문의 수학적 성질을 결합한 대표적인 트리 탐색 문제입니다. 각 경로를 탐색하면서 숫자별 등장 횟수를 배열로 관리하고, 리프 노드에 도달할 때마다 홀수 개수 조건만 확인하면 되기 때문에 전체 시간 복잡도 역시 효율적으로 유지됩니다.