이 문제에서는 하나의 이진 트리(binary tree)와 숫자 K가 주어지며, 트리 내에서 경로에 포함된 노드 값들의 합이 K와 같은 모든 경로를 찾아 출력해야 합니다.
문제의 조건
여기서 말하는 경로는 트리의 어떤 노드에서든 시작할 수 있고 어떤 노드에서든 끝날 수 있습니다. 단, 경로는 항상 위쪽(루트 방향)에서 아래쪽(자식 방향)으로만 진행되어야 하며, 역방향 이동은 허용되지 않습니다. 또한 트리 노드의 값은 양수, 음수, 0 중 어떤 것이든 가능합니다.
예제로 이해하기
다음 예제를 통해 문제를 살펴보겠습니다.
입력: K = 5
출력:
1 3 1
3 2
1 4
위 결과를 보면, 각 경로에 있는 노드 값들의 합이 모두 5가 되는 것을 확인할 수 있습니다.
접근 방법
이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.
모든 노드를 임시 루트로 취급하는 것입니다. 각 노드를 기준점으로 삼고, 해당 노드에서 시작하여 자식 노드들로 뻗어가는 경로 중 노드 값의 합이 K가 되는 경로를 찾습니다.
구체적인 동작 과정은 다음과 같습니다.
1. 현재까지 지나온 경로의 모든 노드 값을 벡터(vector)에 저장합니다.
2. 각 노드를 방문할 때마다, 벡터의 뒤쪽부터 거꾸로 누적합을 계산합니다.
3. 누적합이 K와 일치하는 순간, 그 시점부터 현재 노드까지의 구간을 경로로 출력합니다.
4. 탐색이 끝나면 현재 노드를 벡터에서 제거(pop)하고 부모 노드로 돌아갑니다.
이렇게 뒤쪽부터 합을 검사하면, 중간에 시작하는 경로도 놓치지 않고 모두 찾을 수 있습니다.
C++ 구현 코드
위 알고리즘을 C++로 구현한 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int x){
data = x;
left = right = NULL;
}
};
// 벡터의 i번째 인덱스부터 끝까지 경로를 출력하는 함수
void printPath(const vector<int>& v, int i) {
for (int j = i; j < v.size(); j++)
cout << v[j] << "\t";
cout << "\n";
}
// 합이 K인 경로를 재귀적으로 찾는 함수
void findKSumPath(Node *root, vector<int>& path, int k) {
if (!root)
return;
// 현재 노드를 경로에 추가
path.push_back(root->data);
// 왼쪽과 오른쪽 서브트리를 재귀적으로 탐색
findKSumPath(root->left, path, k);
findKSumPath(root->right, path, k);
// 경로의 뒤쪽부터 거꾸로 누적합을 계산
int f = 0;
for (int j = path.size() - 1; j >= 0; j--){
f += path[j];
if (f == k)
printPath(path, j);
}
// 백트래킹: 현재 노드를 경로에서 제거
path.pop_back();
}
int main() {
/* 트리 생성
1
/ \
3 4
/ \ \
1 2 7
*/
Node *root = new Node(1);
root->left = new Node(3);
root->left->left = new Node(1);
root->left->right = new Node(2);
root->right = new Node(4);
root->right->right = new Node(7);
int k = 5;
cout << "Paths with sum " << k << " are :\n";
vector<int> path;
findKSumPath(root, path, k);
return 0;
}
실행 결과
Paths with sum 5 are −
1 3 1
3 2
1 4
정리
이 알고리즘은 깊이 우선 탐색(DFS)과 백트래킹(backtracking)을 활용합니다. 모든 노드 쌍에 대해 경로를 검사하므로 시간 복잡도는 O(n²)입니다. 여기서 n은 트리의 노드 개수입니다. 노드 값에 음수가 포함될 수 있기 때문에 누적합이 K를 초과하더라도 탐색을 중단할 수 없으며, 끝까지 검사해야 한다는 점이 특징입니다.