주어진 문제에는 N개의 방이 있으며, 이들은 N-1개의 도로로 연결되어 트리 구조를 이룹니다. 각 방에는 시한폭탄이 설치되어 T 시간 후에 동시에 폭발합니다. i번째 방에는 P_i 가치의 보석이 있고, 각 도로를 통과하는 데는 특정 시간이 소요됩니다. 한 사람이 1번 방에서 출발하여 N번 방으로 탈출해야 하며, 도중에 폭탄에 의해 사망하지 않는 선에서 최대한 많은 가치의 보석을 가져가야 합니다. 이때 얻을 수 있는 최대 보석 가치를 찾는 것이 목표입니다.
이 문제는 트리 위에서의 0/1 배낭 문제로 추상화될 수 있습니다. 핵심 아이디어는 1번 방에서 N번 방으로 가는 유일한 경로를 반드시 한 번 지나야 한다는 점입니다. 이 경로에 연결된 다른 '가지(branch)'들을 탐색할 때는 해당 가지로 이동하고 다시 주 경로로 돌아와야 하므로, 해당 가지의 간선들은 왕복으로 두 번씩 통과해야 합니다. 따라서 가지 탐색에 드는 각 간선 비용은 두 배로 계산됩니다.
문제 해결 전략은 다음과 같습니다:
- 먼저 1번 방에서 N번 방까지의 유일 경로를 찾고, 이 경로를 통과하는 데 필요한 총 시간을 계산합니다. 이 시간을 전체 허용 시간 T에서 미리 차감합니다.
- 1번 방에서 N번 방까지의 경로 상에 있는 간선들의 비용을 0으로 설정합니다. 이는 해당 간선 비용을 이미 지불했음을 의미하며, 동적 프로그래밍(DP) 계산 시 고려하지 않도록 합니다.
- 이제 1번 방을 루트로 하는 트리에서 동적 프로그래밍(DP)을 수행합니다. DP[u][j]는 노드 u를 루트로 하는 서브트리에서 j 시간 이내에 얻을 수 있는 최대 보석 가치를 나타냅니다. 이때, DP[u][j]는 노드 u 자체의 가치를 포함하지 않으며, 자식 노드 v의 가치 P_v는 v를 방문할 때 추가됩니다.
동적 프로그래밍 점화식은 다음과 같습니다. 노드 u에서 자식 노드 v로 연결된 간선의 가중치를 w라고 할 때:
for (int current_total_time = max_available_time; current_total_time >= edge_weight_to_v * 2; --current_total_time) {
for (int time_for_child_subtree = 0; time_for_child_subtree <= current_total_time - edge_weight_to_v * 2; ++time_for_child_subtree) {
dp_table[u][current_total_time] = std::max(
dp_table[u][current_total_time],
dp_table[u][current_total_time - edge_weight_to_v * 2 - time_for_child_subtree] + jewel_values[v] + dp_table[v][time_for_child_subtree]
);
}
}여기서 dp_table[u][j]는 u의 자식 서브트리에서 j 시간으로 얻을 수 있는 최대 가치입니다. dp_table[u][current_total_time - edge_weight_to_v * 2 - time_for_child_subtree]는 u의 다른 자식 서브트리들로부터 얻은 가치를 의미하며, jewel_values[v]는 노드 v의 고유 가치, dp_table[v][time_for_child_subtree]는 노드 v의 자식 서브트리들로부터 얻은 가치입니다. edge_weight_to_v * 2는 노드 u에서 v로 갔다가 돌아오는 왕복 비용입니다.
최종 결과는 dp_table[1][remaining_total_time] + jewel_values[1]이 됩니다. jewel_values[1]을 마지막에 더하는 이유는 dp 테이블이 각 노드 자체의 가치를 직접 포함하지 않고 자식 서브트리의 가치만을 누적하기 때문입니다.
구현 예시
아래는 위 전략을 구현한 C++ 코드입니다.
#include <iostream>
#include <vector>
#include <cstring> // for memset
#include <algorithm> // for std::max
// 그래프 간선 정보를 저장하는 구조체
struct Edge {
int target_node;
int weight;
int next_edge_idx; // 다음 간선 인덱스 (인접 리스트 구현용)
};
const int MAX_NODES = 205; // 최대 노드 수 (문제 N은 200까지)
const int MAX_TIME = 555; // 최대 시간 예산 (문제 T는 550까지)
Edge graph_edges[MAX_NODES * 2]; // 간선 배열 (양방향이므로 *2)
int head[MAX_NODES]; // 각 노드의 인접 리스트 시작점
int edge_count; // 현재까지 추가된 간선 수
int parent_node[MAX_NODES]; // 각 노드의 부모 노드 (경로 탐색용)
int edge_from_parent_idx[MAX_NODES]; // 부모에서 현재 노드로 오는 간선의 인덱스
int jewel_values[MAX_NODES]; // 각 노드의 보석 가치
int dp_table[MAX_NODES][MAX_TIME]; // 동적 프로그래밍 테이블
// 그래프 초기화
void initialize_graph() {
edge_count = 0;
memset(head, -1, sizeof(head));
}
// 간선 추가 (양방향)
void add_edge(int u, int v, int w) {
graph_edges[edge_count] = {v, w, head[u]};
head[u] = edge_count++;
graph_edges[edge_count] = {u, w, head[v]};
head[v] = edge_count++;
}
// 1번 노드에서 N번 노드까지의 경로를 찾기 위한 DFS
void find_path_dfs(int u, int p) {
parent_node[u] = p; // u의 부모는 p
for (int i = head[u]; i != -1; i = graph_edges[i].next_edge_idx) {
int v = graph_edges[i].target_node;
if (v == p) continue; // 부모 노드는 건너뛰기
edge_from_parent_idx[v] = i; // v로 오는 간선의 인덱스 기록
find_path_dfs(v, u);
}
}
// 트리 DP 수행 DFS
void solve_tree_dp(int u, int p, int max_available_time) {
// dp_table[u][t]는 현재 노드 u의 자식 서브트리에서 t 시간 이내에 얻을 수 있는 최대 가치
// u 자체의 가치는 포함하지 않음.
for (int i = head[u]; i != -1; i = graph_edges[i].next_edge_idx) {
int v = graph_edges[i].target_node;
int current_edge_weight = graph_edges[i].weight;
if (v == p) continue;
// 만약 남은 시간이 자식 노드 v로 왕복하는 데 필요한 최소 시간보다 적으면, 탐색 불가
if (max_available_time < current_edge_weight * 2) continue;
// 자식 서브트리 먼저 처리
solve_tree_dp(v, u, max_available_time);
// 0/1 배낭 스타일로 현재 노드 u의 dp_table 업데이트
// current_total_time은 u의 서브트리 전체에 할당된 시간 (v의 서브트리 포함)
for (int current_total_time = max_available_time; current_total_time >= current_edge_weight * 2; --current_total_time) {
// time_for_child_subtree는 자식 v의 서브트리에서 사용할 시간
for (int time_for_child_subtree = 0; time_for_child_subtree <= current_total_time - current_edge_weight * 2; ++time_for_child_subtree) {
dp_table[u][current_total_time] = std::max(
dp_table[u][current_total_time],
dp_table[u][current_total_time - current_edge_weight * 2 - time_for_child_subtree] + jewel_values[v] + dp_table[v][time_for_child_subtree]
);
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_nodes, total_time_limit;
while (std::cin >> N_nodes >> total_time_limit) {
initialize_graph();
for (int i = 0; i < N_nodes - 1; ++i) {
int u_node, v_node, edge_w;
std::cin >> u_node >> v_node >> edge_w;
add_edge(u_node, v_node, edge_w);
}
for (int i = 1; i <= N_nodes; ++i) {
std::cin >> jewel_values[i];
}
// 1번에서 N번까지의 경로 탐색
parent_node[1] = 0; // 1번 노드의 부모는 없음 (가상의 0)
find_path_dfs(1, 0); // 1번을 루트로 하여 부모 정보 채우기
int path_total_cost = 0;
// N번에서 1번까지 역추적하며 경로 비용 계산 및 해당 간선 가중치 0으로 설정
for (int current_node = N_nodes; current_node != 1; current_node = parent_node[current_node]) {
int edge_idx = edge_from_parent_idx[current_node];
path_total_cost += graph_edges[edge_idx].weight;
// 경로 간선 비용을 0으로 설정 (이미 지불된 것으로 간주)
graph_edges[edge_idx].weight = 0;
graph_edges[edge_idx ^ 1].weight = 0; // 반대 방향 간선도 0으로 설정
}
// 남은 시간 예산 계산
total_time_limit -= path_total_cost;
if (total_time_limit < 0) {
std::cout << "시간 부족으로 탈출 불가!\n";
continue;
}
// DP 테이블 초기화
memset(dp_table, 0, sizeof(dp_table));
// 트리 DP 수행
solve_tree_dp(1, 0, total_time_limit);
// 최종 결과: 1번 노드 자체의 가치 + 나머지 서브트리에서 얻은 최대 가치
std::cout << dp_table[1][total_time_limit] + jewel_values[1] << "\n";
}
return 0;
}