문제 소개
이진 트리(binary tree)와 목표값 k가 주어졌을 때, 어떤 노드에서 시작해 그 아래 자손 노드로 내려가는 경로 중에서 노드 값들의 합이 정확히 k가 되는 고유한 경로의 개수를 세는 프로그램을 작성해 보겠습니다.
예를 들어 다음과 같은 이진 트리가 있다고 가정해 봅시다.
이때 k = 5라면 출력 결과는 2가 됩니다. 합이 5가 되는 경로가 [2, 3]과 [1, 4], 총 두 가지이기 때문입니다.
접근 방법: 접두사 합(Prefix Sum) 활용
이 문제는 접두사 합(prefix sum) 기법과 DFS(깊이 우선 탐색)를 조합하면 효율적으로 해결할 수 있습니다. 루트에서 현재 노드까지의 누적 합을 추적하고, 해시 맵에 각 접두사 합이 등장한 횟수를 저장합니다. 현재 접두사 합에서 target을 뺀 값이 맵에 존재한다면, 그 등장 횟수만큼 합이 k가 되는 경로가 존재한다는 의미입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- count := 키 0에 값 1을 미리 저장한 맵(Counter)으로 초기화
- ans := 0, prefix := 0으로 초기화
- dfs() 함수를 정의합니다. 이 함수는 노드를 인자로 받습니다.
- 노드가 null이 아니라면:
- prefix := prefix + 현재 노드의 값
- ans := ans + count[prefix - target] (키가 없으면 0으로 처리)
- count[prefix] := count[prefix] + 1
- dfs(노드의 왼쪽 자식) 호출
- dfs(노드의 오른쪽 자식) 호출
- count[prefix] := count[prefix] - 1 (백트래킹으로 상태 복원)
- prefix := prefix - 현재 노드의 값 (백트래킹으로 상태 복원)
- 메인 메서드에서는 dfs(root)를 호출한 뒤 ans를 반환합니다.
여기서 백트래킹(backtracking)이 중요한 이유는, 한쪽 서브트리 탐색이 끝난 후 다른 분기를 탐색할 때 이전 경로의 접두사 정보가 남아 있으면 잘못된 경로까지 세어질 수 있기 때문입니다. 재귀 호출이 끝나면 반드시 count와 prefix를 원래 상태로 되돌려 주어야 합니다.
파이썬 구현 예제
from collections import Counter
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root, target):
count = Counter([0])
ans = prefix = 0
def dfs(node):
nonlocal ans, prefix
if node:
prefix += node.val
ans += count[prefix - target]
count[prefix] += 1
dfs(node.left)
dfs(node.right)
# 백트래킹: 다른 분기 탐색 시 영향을 주지 않도록 상태 복원
count[prefix] -= 1
prefix -= node.val
dfs(root)
return ans
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(1)
root.right.left.right = TreeNode(2)
k = 5
print(ob.solve(root, k))
입력
root = TreeNode(3) root.left = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(1) root.right.left.right = TreeNode(2) 5
출력
2
복잡도 분석
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다(n은 노드의 개수). 또한 해시 맵과 재귀 호출 스택에 공간을 사용하므로 공간 복잡도 역시 최악의 경우 O(n)입니다. 모든 가능한 경로를 일일이 확인하는 브루트포스 방식(O(n²))보다 훨씬 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.