이 글에서는 C++을 사용해 K진(K-ary) 트리에서 총 가중치가 W인 경로의 개수를 계산하는 방법을 알아보겠습니다. K진 트리란 각 노드가 정확히 K개의 자식 노드를 가지는 트리를 말하며, 한 노드에서 자식 노드들로 이어지는 간선에는 1부터 K까지의 가중치가 순서대로 부여됩니다.
우리가 구해야 하는 값은 루트에서 시작하는 경로 중 누적 가중치가 정확히 W이고, 가중치가 M 이상인 간선을 적어도 하나 포함하는 경로의 개수입니다. 예시는 다음과 같습니다.
입력 : W = 4, K = 3, M = 2 출력 : 6
이 문제는 동적 계획법(DP)을 활용하면 시간 복잡도와 공간 복잡도를 크게 줄일 수 있습니다. 메모이제이션(memoization)을 적용하면 프로그램 실행 속도가 훨씬 빨라져, 더 큰 입력 제한에서도 충분히 활용할 수 있습니다.
접근 방법
이 접근법에서는 트리를 순회하면서 다음 두 가지 정보를 함께 추적합니다.
- 현재까지 선택한 경로에 가중치가 M 이상인 간선이 포함되어 있는지 여부
- 경로의 누적 가중치가 W와 일치하는지 여부
누적 가중치가 정확히 W가 되었고, 가중치 M 이상인 간선이 하나 이상 포함되어 있다면 정답 개수를 1 증가시킵니다.
코드 구현
#include <bits/stdc++.h>
using namespace std;
int solve(int DP[][2], int W, int K, int M, int used){
if (W < 0) // W가 0보다 작아지면 0을 반환
return 0;
if (W == 0) {
if (used) // used가 참이면 1을 반환
return 1; // 가중치 M 이상인 간선이 최소 하나 포함된 경우
return 0;
}
if (DP[W][used] != -1) // DP[W][used]가 -1이 아니라면 이미 계산된 상태
return DP[W][used];
int answer = 0;
for (int i = 1; i <= K; i++) {
if (i >= M)
answer += solve(DP, W - i, K, M, used | 1); // 조건이 참이면 used를 1로 변경
else
answer += solve(DP, W - i, K, M, used);
}
return answer;
}
int main(){
int W = 3; // 목표 가중치
int K = 3; // 각 노드가 가지는 자식 노드의 수
int M = 2; // 가중치 2 이상인 간선을 반드시 포함해야 함
int DP[W + 1][2]; // DP 배열
memset(DP, -1, sizeof(DP)); // 배열을 -1로 초기화
cout << solve(DP, W, K, M, 0) << "\n";
return 0;
}
출력
3
코드 설명
이 접근법의 핵심은 두 가지 상태를 동시에 추적하는 것입니다. 첫째, 가중치 M 이상인 간선이 경로에 최소 한 번이라도 포함되었는지 여부를 used 플래그로 관리합니다. 둘째, 재귀 호출을 통해 남은 가중치를 하나씩 줄여가며 그 값이 정확히 0이 되는 지점, 즉 총 가중치가 W인 경로를 확인합니다.
조건을 만족하는 경로를 찾으면 정답을 1 증가시키고, 해당 상태는 DP 배열에 기록합니다. 이미 계산된 상태는 배열에서 즉시 가져오므로 중복 연산이 발생하지 않습니다. 이 과정을 통해 모든 가능한 경로를 탐색하되, 가중치가 M 이상인 간선을 최소 하나 포함하는 경로만 최종 결과에 반영됩니다.
결론
이 글에서는 동적 계획법을 활용하여 K진 트리에서 총 가중치가 W이면서 가중치 M 이상인 간선을 포함하는 경로의 개수를 O(W*K) 시간 복잡도로 구하는 방법을 살펴보았습니다.
단순 재귀 탐색과 달리 메모이제이션을 적용하면 동일한 하위 문제를 반복해서 계산하지 않으므로 성능이 크게 향상됩니다. 이러한 패턴은 트리 구조에서 특정 조건을 만족하는 경로를 세는 다양한 문제에 널리 응용할 수 있습니다.