다지 트리 배낭 문제 (Multi-ary Tree Knapsack Problem)
이전에는 이진 트리를 기반으로 한 문제를 다루었지만, 이제는 난이도를 높여 다지 트리(multi-ary tree) 구조에 적용되는 동적 계획법(DP)을 살펴보겠습니다. 다지 트리는 각 노드가 여러 자식 노드를 가질 수 있는 형태입니다. 이 경우, 단순한 이진 트리 DP 방식으로는 해결하기 어렵습니다. 대신, 배낭 문제(knapsack problem)의 아이디어를 트리에 적용하는, 소위 '트리 배낭' 기법을 활용할 수 있습니다.
트리 배낭 문제의 핵심은 각 노드를 기준으로 해당 노드를 포함하는 서브트리에서 특정 개수의 노드를 선택하여 최대 가치를 얻는 것입니다. 이는 마치 배낭에 물건을 담는 과정과 유사합니다. 한 노드의 DP 상태는 자신의 자식 노드들의 DP 상태를 병합하여 갱신됩니다.
dp[u][k]를 노드 u를 루트로 하는 서브트리에서 k개의 노드를 선택했을 때 얻을 수 있는 최대 가치라고 정의합니다. DP 계산은 깊이 우선 탐색(DFS)을 통해 리프 노드부터 시작하여 루트 노드 방향으로 진행됩니다.
- 초기화: 노드
u의 DP 테이블을 초기화합니다.dp[u][0] = 0(0개의 노드 선택 시 가치 0). 만약k > 0개의 노드를 선택하고u가 반드시 포함되어야 한다면,dp[u][1] = node_values[u]로 시작하고, 그 외의k에 대해서는node_values[u]로 초기화합니다. - 자식 노드 병합: 노드
u의 각 자식v에 대해 재귀적으로dp[v]를 계산한 후,dp[v]테이블을dp[u]테이블에 병합합니다. 이때,dp[u]의 기존 상태(u와 이미 처리된 자식들로부터 얻은 값)와dp[v]의 상태를 결합합니다.dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j])여기서i는u의 서브트리에서 선택할 총 노드 개수,j는 자식v의 서브트리에서 선택할 노드 개수입니다.i-j는u와 나머지 자식들에서 선택할 노드 개수가 됩니다. 이 과정은 일반적인 0/1 배낭 문제의 점화식과 유사하게,i와j를 역순으로 반복하며 수행됩니다.
예시 코드 (트리 배낭)
#include <iostream>#include <vector>#include <algorithm> // std::max#include <cstring> // std::memsetconst int MAX_NODES = 110; // 최대 노드 수const int MAX_SELECT_COUNT = 110; // 선택할 최대 노드 개수struct AdjNode { int target; // 연결된 노드 int val_if_child; // target 노드의 값 (부모로부터 연결될 때)};std::vector<AdjNode> adj[MAX_NODES]; // 인접 리스트: (목표 노드, 해당 노드의 값)int nodeValues[MAX_NODES]; // 각 노드의 실제 값 (이 코드는 이를 populate하는 방식에 따라 결정됨)int dp[MAX_NODES][MAX_SELECT_COUNT]; // dp[u][k]: u 서브트리에서 k개 노드 선택 시 최대 가치int totalNodes, maxNodesToPick; // 전체 노드 수, 선택할 최대 노드 수// DFS를 이용하여 트리 배낭 문제 해결void solveTreeKnapsack(int currentNode, int parentNode) { // 현재 노드(currentNode)의 DP 테이블 초기화 // k=0일 때는 0의 가치. dp[currentNode][0] = 0; // k > 0 일 때는 currentNode를 선택했다고 가정하고 그 가치를 초기값으로 설정 // 이후 자식 노드에서 추가되는 가치를 더해 나감. // 만약 currentNode를 선택하지 않을 수 있다면 이 초기화는 달라져야 함. // 이 문제에서는 루트 노드(1번)는 가치가 0이며, 다른 노드들은 부모-자식 관계의 에지로부터 가치를 부여받음. // 예를 들어, 입력 'x y z'가 (x, y) 에지이며 y의 값이 z임을 의미한다면, // nodeValues[currentNode]는 currentNode의 가치를 저장해야 함. // 여기서는 z값이y의 값으로 간주되므로, nodeValues배열을 직접 설정합니다. for (int k = 1; k <= maxNodesToPick; ++k) { dp[currentNode][k] = nodeValues[currentNode]; } // 각 자식 노드에 대해 재귀 호출 및 DP 테이블 병합 for (const auto& edge : adj[currentNode]) { int childNode = edge.target; if (childNode == parentNode) { continue; } // 재귀 호출 전, childNode의 실제 값 설정 (original 코드의 dfsquan 역할) // 여기서는edge.val_if_child가 childNode의 값이라고 가정합니다. nodeValues[childNode] = edge.val_if_child; solveTreeKnapsack(childNode, currentNode); // 자식 서브트리 DP 계산 // 자식 노드의 결과를 현재 노드의 DP 테이블에 병합 (배낭 문제와 유사) // i: 현재 노드 서브트리에서 선택할 총 노드 수 // j: 자식 노드 서브트리에서 선택할 노드 수 for (int i = maxNodesToPick; i >= 1; --i) { for (int j = 0; j < i; ++j) { // dp[currentNode][i - j]는 currentNode와 이미 처리된 자식들로부터 i-j개의 노드를 선택한 값 // dp[childNode][j]는 childNode 서브트리에서 j개의 노드를 선택한 값 dp[currentNode][i] = std::max(dp[currentNode][i], dp[currentNode][i - j] + dp[childNode][j]); } } }}int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> totalNodes >> maxNodesToPick; // DP 테이블 초기화 (모든 값 0으로, 음수 가치가 있을 경우 -infinity로 초기화 필요) for (int i = 0; i < MAX_NODES; ++i) { for (int j = 0; j < MAX_SELECT_COUNT; ++j) { dp[i][j] = 0; } } // 루트 노드(1번 노드)의 값은 0으로 가정 (원문 코드의 동작 방식 추론) nodeValues[1] = 0; // 간선 정보 입력 for (int i = 0; i < totalNodes - 1; ++i) { int u, v, value_of_v; std::cin >> u >> v >> value_of_v; // value_of_v는 v노드의 값으로 간주 (원문dfsquan동작 방식 추론) adj[u].push_back({v, value_of_v}); adj[v].push_back({u, value_of_v}); // 양방향 간선 추가 } solveTreeKnapsack(1, -1); // 1번 노드를 루트로 하여 DFS 시작 (-1은 가상의 부모) std::cout << dp[1][maxNodesToPick + 1] << std::endl; // 원문 코드에 따라 q+1 출력 // maxNodesToPick이 0부터 시작하는 인덱스라면 maxNodesToPick까지, // 1부터 시작하는 인덱스라면 maxNodesToPick이 해당 개수를 의미할 것. // 원문에서는 dp[1][q+1]을 출력하므로, q가 edge의 개수를 의미하고 q+1은 노드의 개수를 의미할 가능성도 있음. // 여기서는 maxNodesToPick이 선택할 '노드' 개수를 의미한다고 가정하고, 원문과 동일하게maxNodesToPick + 1을 출력. // 문제의 정확한 정의에 따라 dp[1][maxNodesToPick]또는dp[1][maxNodesToPick + 1]이 될 수 있음.}```<p>위 코드에서 nodeValues</p> 배열은 각 노드의 가치를 명시적으로 저장합니다. 원문의 dfsquan 함수와 v[edge[i].dian] = edge[i].quan; 부분은 이 nodeValues 배열을 구성하는 독특한 방식으로 해석되었습니다. 즉, 입력 x y z에서 z는 노드 y의 가치로 사용되며, 1번 노드(루트)는 특별히 0의 가치를 가진다고 가정합니다. 출력 시 dp[1][maxNodesToPick + 1]은 원문 코드의 dp[1][q+1]에 맞춘 것으로, 선택할 노드 개수가 maxNodesToPick일 때의 결과값을 의미합니다.
트리에서의 최대 경로 합 (Maximum Path Sum in a Tree) 다음으로, 가중치 없는 트리의 노드들에 값이 주어졌을 때, 트리의 어떤 두 노드를 잇는 경로 중 노드 값들의 합이 최대가 되는 경로를 찾는 문제입니다. 이 문제 또한 동적 계획법으로 효율적으로 해결할 수 있습니다. 이 문제를 해결하기 위해 두 가지 DP 상태를 고려할 수 있습니다:
dp[u]: 노드u를 포함하며,u에서 시작하여u의 서브트리 아래로만 뻗어 나가는 경로 중 최대 합. 즉,u를 '시작점'으로 하는 최대 경로 합.max_global_sum: 트리의 모든 경로 중에서 노드 값의 합이 최대가 되는 값. 이 경로는 어떤 노드를 지나거나, 특정 서브트리에 완전히 포함될 수 있습니다.dp[u]를 계산하면서 동시에max_global_sum을 갱신합니다. DFS를 통해 리프 노드부터 시작하여 올라오면서 계산합니다.- 초기화:
dp[u]는 최소한u자신만의 값을 가질 수 있으므로,dp[u] = node_values[u]로 초기화합니다.max_global_sum도node_values[u]와 비교하여 갱신합니다. - 자식 노드 처리: 노드
u의 각 자식v에 대해 재귀적으로solveMaxPath(v, u)를 호출합니다. 자식v의 DP 계산이 완료되면, 이를 사용하여u의 DP 상태와max_global_sum을 갱신합니다. max_global_sum갱신:max(max_global_sum, dp[v]): 자식v를 루트로 하는 서브트리 안에서 최대 경로가 발생할 수 있습니다.max(max_global_sum, dp[u] + dp[v]):u를 거쳐서 양쪽 자식 서브트리로 뻗어 나가는 경로가 최대가 될 수 있습니다. 여기서dp[u]는 현재까지u의 값을 포함하고 이미 처리된 자식 중 최대 경로 값을 더한 상태입니다.
dp[u] 갱신: u를 시작점으로 하는 경로가 더 길어질 수 있습니다. dp[u] = max(dp[u], node_values[u] + dp[v]). 즉, u의 값에 자식 v에서 얻을 수 있는 최대 경로 값을 더하는 것을 고려합니다. (dp[v]는 음수가 아닐 때만 유효하며, 음수일 경우 더하지 않는 것이 더 큰 값을 줄 수 있습니다.)
예시 코드 (최대 경로 합)
#include <iostream>#include <vector>#include <algorithm> // std::max#include <cstring> // std::memset#define INF 2e18 // 충분히 큰 음수 또는 양수 표현을 위한 값// 노드 값이나 경로 합이 음수일 수 있으므로 long long을 사용typedef long long ll; const int MAX_NODE_COUNT_PATH = 100010;struct PathEdge { int neighborNode;};std::vector<PathEdge> pathAdj[MAX_NODE_COUNT_PATH]; // 인접 리스트ll pathNodeValues[MAX_NODE_COUNT_PATH]; // 각 노드의 값ll pathDp[MAX_NODE_COUNT_PATH]; // pathDp[u]: u에서 아래로 뻗어가는 최대 경로 합ll maxGlobalPathSum = -INF; // 전체 트리에서 최대 경로 합 (음수 포함 가능성 때문에 초기화 중요)int totalNodesPath; // 전체 노드 수// DFS를 이용하여 최대 경로 합 문제 해결void solveMaxPath(int currentNode, int parentNode) { // pathDp[currentNode] 초기화: 최소한 자기 자신의 값만 포함하는 경로 pathDp[currentNode] = pathNodeValues[currentNode]; // maxGlobalPathSum 갱신: 노드 하나만으로 이루어진 경로도 고려 maxGlobalPathSum = std::max(maxGlobalPathSum, pathNodeValues[currentNode]); ll maxChildPath1 = 0; // currentNode에서 아래로 뻗어갈 수 있는 최대 경로 ll maxChildPath2 = 0; // currentNode에서 아래로 뻗어갈 수 있는 두 번째로 큰 경로 for (const auto& edge : pathAdj[currentNode]) { int childNode = edge.neighborNode; if (childNode == parentNode) { continue; } solveMaxPath(childNode, currentNode); // 자식 서브트리 재귀 호출 // 자식 서브트리의 최대 경로 합이 음수이면, 그 경로를 포함하는 것이 이득이 아님 ll childPathValue = std::max(0LL, pathDp[childNode]); // pathDp[childNode] > 0 일 때만 고려하는 것이 올바름. // 왜냐하면 음수 경로를 더하면 오히려 전체 합이 줄어들기 때문. // maxGlobalPathSum 갱신: // 1. currentNode를 거쳐 현재까지의 최대 경로 + 자식 경로 // 이는 pathNodeValues[currentNode] + 현재까지의 maxChildPath1 + childPathValue 를 의미 // (즉, currentNode를 중심으로 두 개의 가장 큰 자식 경로를 연결) maxGlobalPathSum = std::max(maxGlobalPathSum, pathNodeValues[currentNode] + maxChildPath1 + childPathValue); // pathDp[currentNode] 갱신: // currentNode에서 시작하여 아래로 뻗어가는 최대 경로. // 이는 currentNode의 값에 자식들 중 가장 큰 경로를 더한 값. pathDp[currentNode] = std::max(pathDp[currentNode], pathNodeValues[currentNode] + childPathValue); // maxChildPath1 및 maxChildPath2 갱신 if (childPathValue > maxChildPath1) { maxChildPath2 = maxChildPath1; maxChildPath1 = childPathValue; } else if (childPathValue > maxChildPath2) { maxChildPath2 = childPathValue; } } // 이 시점에서 pathDp[currentNode]는 이미 currentNode의 값과 가장 큰 하나의 자식 경로를 더한 상태. // maxGlobalPathSum은 currentNode를 중심으로 두 개의 가장 큰 자식 경로를 연결하는 경로도 고려. // 기존의 maxGlobalPathSum = std::max(maxGlobalPathSum, pathDp[root] + dp[edge[i].dian]);과 // dp[root]=max(dp[root],a[root]+dp[edge[i].dian]);의 로직은 // 사실 maxChildPath1/2를 명시적으로 트래킹하는 방식과 동일하게 작동함. // 원본 코드와 같이 pathDp[currentNode]에 가장 큰 하나의 자식 경로를 더하고, // maxGlobalPathSum에 pathNodeValues[currentNode] + maxChildPath1 + maxChildPath2를 더하여 갱신하는 것이 명확합니다. // 위의 루프에서 이미 maxGlobalPathSum = std::max(maxGlobalPathSum, pathNodeValues[currentNode] + maxChildPath1 + childPathValue); // 이 부분이 사실상pathNodeValues[currentNode] + 가장 큰 자식 경로 + 두 번째로 큰 자식 경로를 고려하는 것입니다. // 최종적으로 maxGlobalPathSum은 max(maxGlobalPathSum, pathNodeValues[currentNode] + maxChildPath1 + maxChildPath2)로 한 번 더 갱신합니다. // 그러나 위 루프의 갱신 방식이 이미 모든 경우를 커버합니다.}int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> totalNodesPath; // 노드 값 입력 for (int i = 1; i <= totalNodesPath; ++i) { std::cin >> pathNodeValues[i]; } // 인접 리스트 초기화 (memset 대신 clear 사용) for(int i = 0; i <= totalNodesPath; ++i) { pathAdj[i].clear(); } // 간선 정보 입력 for (int i = 0; i < totalNodesPath - 1; ++i) { int u, v; std::cin >> u >> v; pathAdj[u].push_back({v}); pathAdj[v].push_back({u}); } // 최대 경로 합 계산 DFS 시작 solveMaxPath(1, -1); // 1번 노드를 루트로 간주 std::cout << maxGlobalPathSum << std::endl; return 0;}```<p>이 코드에서 pathDp[currentNode]</p>는 currentNode를 최상단으로 하는 단일 경로의 최대 합을 추적합니다. maxGlobalPathSum은 트리의 모든 가능한 경로 중에서 최대 합을 저장합니다. maxGlobalPathSum을 갱신할 때 pathNodeValues[currentNode] + maxChildPath1 + maxChildPath2를 고려하는 것은 currentNode를 통과하는 가장 긴 경로(두 개의 가장 큰 자식 경로를 연결)를 찾는 핵심 아이디어입니다. std::max(0LL, pathDp[childNode])를 사용하여 음수 경로가 전체 합을 감소시키지 않도록 방지하는 것이 중요합니다. 이 기법은 노드 값이 음수일 수 있는 경우에 특히 유용합니다.