백준_1949_우수 마을

우수 마을

문제

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.

이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
   마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 2. '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
2. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.
   각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 '우수 마을'을 선정하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 '우수 마을'의 주민 수의 총 합을 출력한다.

예제 입력 1

7
1000 3000 4000 1000 2000 2000 7000
1 2
2 3
4 3
4 5
6 2
6 7

예제 출력 1

14000

풀이 및 해설

출력값: 우수 마을의 주민 수 총합 구하기

1. 한 마을이 우수마을이면 인접해있는 마을은 우수마을일 수 없음
2. 우수 마을로 선정되지 못한 마을은 적어도 하나의 우수 마을과 인접해 있어야 함

→ 트리 형태 + DP 이용

• DP[마을 번호][우수마을 여부]
• Bottom-Up 방식 이용

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 마을의 수
const peopleOfCity = [0];
peopleOfCity.push(...input[1].split(' ').map(Number)); // 각 마을의 주민 수
const v = Array.from({ length: N + 1 }, () => []); // 인접한 마을 정보
for (let i = 2; i < N + 1; i++) {
  const [city1, city2] = input[i].split(' ').map(Number);
  v[city1].push(city2);
  v[city2].push(city1);
}

const dp = Array.from({ length: N + 1 }, () => new Array(2).fill(0)); // dp[마을번호][우수마을인지 아닌지(우수마을: 0, 우수마을X: 1)]

const dfs = (cityNum, parentCity) => {
  for (const nearCity of v[cityNum]) {
    if (nearCity !== parentCity) {
      dfs(nearCity, cityNum);
      // 부모 마을이 우수마을인 경우, 자식 마을은 우수마을이면 X
      dp[cityNum][0] += dp[nearCity][1];
      // 부모 마을이 우수마을이 아닌 경우,
      // 자식 마을은 우수마을이거나 우수마을 아닐 수 있음
      dp[cityNum][1] += Math.max(dp[nearCity][0], dp[nearCity][1]);
    }
  }
  dp[cityNum][0] += peopleOfCity[cityNum]; // 우수마을의 주민 수 더하기
};

dfs(1, 0);
console.log(Math.max(dp[1][0], dp[1][1]));