[백준 1949] 우수 마을 (C#, C++) - soo:bak

문제 링크

1949번 - 우수 마을

설명

트리 구조의 마을들이 주어질 때, 인접한 두 마을을 동시에 우수 마을로 선정할 수 없다는 조건 하에서 우수 마을 주민 수의 합을 최대로 하는 문제입니다.

접근법

각 마을에 대해 우수 마을로 선정하는 경우와 선정하지 않는 경우를 나누어 생각합니다.

먼저 어떤 마을을 우수 마을로 선정하면, 인접한 자식 마을들은 모두 선정할 수 없습니다. 따라서 그 마을의 주민 수에 자식들을 선정하지 않았을 때의 최댓값들을 더합니다.

다음으로 어떤 마을을 선정하지 않으면, 자식 마을들은 선정해도 되고 안 해도 됩니다. 따라서 각 자식에 대해 선정했을 때와 하지 않았을 때 중 더 큰 값을 선택하여 더합니다.

깊이 우선 탐색으로 리프 노드부터 값을 계산해 올라오면, 루트에서 선정한 경우와 하지 않은 경우 중 더 큰 값이 답이 됩니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static int n;
  static int[] pop = Array.Empty<int>();
  static List<int>[] adj = Array.Empty<List<int>>();
  static int[,] dp = new int[0, 0];
  static bool[] vis = Array.Empty<bool>();

  static void Dfs(int u) {
    vis[u] = true;
    dp[u, 1] = pop[u];
    foreach (var v in adj[u]) {
      if (vis[v]) continue;
      Dfs(v);
      dp[u, 1] += dp[v, 0];
      dp[u, 0] += Math.Max(dp[v, 0], dp[v, 1]);
    }
  }

  static void Main() {
    n = int.Parse(Console.ReadLine()!);
    pop = new int[n + 1];
    var parts = Console.ReadLine()!.Split();
    for (var i = 1; i <= n; i++) pop[i] = int.Parse(parts[i - 1]);

    adj = new List<int>[n + 1];
    for (var i = 1; i <= n; i++) adj[i] = new List<int>();
    for (var i = 0; i < n - 1; i++) {
      var e = Console.ReadLine()!.Split();
      var a = int.Parse(e[0]);
      var b = int.Parse(e[1]);
      adj[a].Add(b);
      adj[b].Add(a);
    }

    dp = new int[n + 1, 2];
    vis = new bool[n + 1];
    Dfs(1);
    Console.WriteLine(Math.Max(dp[1, 0], dp[1, 1]));
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi pop(n + 1);
  for (int i = 1; i <= n; i++) cin >> pop[i];

  vvi adj(n + 1);
  for (int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  vector<array<int, 2>> dp(n + 1, {0, 0});
  vector<char> vis(n + 1, 0);
  function<void(int)> dfs = [&](int u) {
    vis[u] = 1;
    dp[u][1] = pop[u];
    for (int v : adj[u]) {
      if (vis[v]) continue;
      dfs(v);
      dp[u][1] += dp[v][0];
      dp[u][0] += max(dp[v][0], dp[v][1]);
    }
  };
  dfs(1);
  cout << max(dp[1][0], dp[1][1]) << "\n";

  return 0;
}