백준 25515 G4 트리 노드 합의 최대값

Date/Lastmod: 04-16/25
Section: PS

Title: 백준 25515 G4 트리 노드 합의 최대값
Ps-Tags: 동적 계획법트리 누적합깊이 우선 탐색
Solved: 04-17/25

#¹ 알고리즘 설명

i번 노드의 번호를 ni라고 하고, i번 노드의 값을 vi라고 하자.

#² `dp`의 정의

dpi를 다음과 같이 정의하자.

dpi는 ni를 루트로 하는 서브트리에서, 노드를 방문하여 만들 수 있는 값의 최대치.

#² 노드가 하나일 때

노드가 하나일 때부터 차근 차근 계산해보자.

당연하게도, n0을 루트로 하고 노드가 n0 하나 뿐인 트리에서 모든 노드를 방문하여 만들 수 있는 값의 최대치 dp0은 v0이다.

#² 자식이 있을 때

조금 더 복잡한 예를 보자.

이제 조금의 생각이 필요하다.

n0부터 방문하여, dp0을 구하려고 하는데, n0에는 자식이 둘 있다.

n0의 자식은 n1과 n2 둘인데, n0 입장에서는 n1과 n2만 보이고, 자신의 자식들이 자식을 가지는지 알 수 없는 상황이다.

하지만 n0이 계산하고 싶은 것은 dp0이지, 자식들의 자식 존재 여부가 아니다.

dp0의 정의를 되새겨 보면, dp0는 n0를 루트로 하는 서브트리에서, 노드를 방문하여 만들 수 있는 값의 최대치이다. 이걸 어떻게 구할까?

트리를 서브 트리로 쪼개기

이 그림에서, n0을 루트로 하는 서브트리는, 다시 n0과 n1을 루트로 하는 서브트리, n2를 루트로 하는 서브트리로 나눌 수 있다.

이렇게 나눈 경우, n1을 루트로 하는 서브트리에서 노드를 방문하여 만들 수 있는 최대값과, n2를 루트로 하는 서브트리에서 노드를 방문하여 만들 수 있는 최대값, 그리고 n0 자체의 값을 더하면 dp0이라고 할 수 있지 않을까?

그러니까, dp0 = v0 + dp1 + dp2라고 할 수 있지 않을까?

아예 방문 자체를 않는 것이 이득인 서브트리

결론적으로 말하면 dp0 = v0 + dp1 + dp2가 아니다.

문제를 보면 vi는 음수가 될 수 있고, 때문에 어떤 노드를 루트로 하는 서브트리의 노드를 모두 방문함으로서 얻는 최대 값 또한 음수가 될 수 있다.

또한, 문제에서 모든 노드를 반드시 방문할 필요는 없다고 하였다.

예를 들어, dp1이 결국 음수가 나왔다고 가정하자. 그러면, n0 입장에서는 n1 쪽 경로는 아예 방문하지 않는 것이 dp0을 최대로 만들기 위해 가장 좋은 전략이다.

식으로는 어떻게 표현할까

dp0 = v0 + dp1 + dp2를 위 논리에 맞게 바꿔 표현해 보자.

dp1, dp2가 양수인 경우에만 더해주면 된다.

때문에 식은 다음 처럼 표현할 수 있다.

dp0 = v0 + max(0, dp1) + max(0, dp2)

간단하게, 0과 dpi 중에 더 큰것을 더하면, 음수인 경우 0이 더해지므로 결과에 아무런 영향을 끼칠 수 없게 된다.

#² 더 복잡한 예

위상적으로 바로 이전의 예와 별 차이는 없다.

결과적으로, dpi를 계산할 때에는, 할 수 있는 한 최대로 트리를 깊게 타고 들어가 리프 노드까지 도달해야 한다. 왜냐하면, 리프 노드는 자손이 없기 때문에 dp 값이 자기 자신의 값으로 고정되기 때문이다.

그리고 역순으로 타고 올라오면서, 계산한 리프 노드들의 dp값으로, 서브트리 루트의 dp값들을 갱신해 나가면서 최종적으로 루트의 dp값을 갱신한다.

이에 가장 적절한 알고리즘은 단연 DFS이다.

#¹ 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <climits>
#include <functional>
#include <algorithm>

using namespace std;
using ll = long long;

int n;
vector<int> node_vals;
vector<vector<int>> tree;
vector<ll> dp;

constexpr int NO_PARENT = -1;

void tree_dfs(int n_idx, int p_idx) {
  // 일단 자기 자신의 값으로 초기화 해 두고 (dpi = v0)
  dp[n_idx] = node_vals[n_idx];

  // 자손이 있다면 있는 대로 순회
  // 만일 자손이 없으면(리프 노드), dpi = v0
  for (const int& c_idx: tree[n_idx]) {
    // 부모는 필요 없음
    if (c_idx == p_idx) {
      continue;
    }

    // 자식의 값을 갱신할 수 있을 때까지 타고 내려가서 갱신
    tree_dfs(c_idx, n_idx);

    dp[n_idx] += max(0ll, dp[c_idx]); // (dpi = v0 + dpc0 + dpc1 ...)
  }
}

int main() {
  cin >> n;

  node_vals.resize(n);
  tree.resize(n);
  dp.resize(n);

  // 간선 입력
  for (int i = 0; i < n - 1; ++i) {
    int p, c; cin >> p >> c;

    tree[p].push_back(c);
    tree[c].push_back(p);
  }

  // 노드 값 입력
  for (int i = 0; i < n; ++i) {
    cin >> node_vals[i];
  }

  // dp 배열 채우기
  tree_dfs(0, NO_PARENT);

  // 출력
  cout << dp[0];
}

백준 25515 G4 트리 노드 합의 최대값

#1 알고리즘 설명

#2 dp의 정의

#2 노드가 하나일 때

#2 자식이 있을 때

#2 더 복잡한 예

#1 코드