[boj] 1949. 우수 마을 (node.js)

문제 요약

BOJ 1949 우수 마을

• 입력: 마을의 수, 연결된 마을들, 주민 수가 주어진다.
• 출력: 주민 수의 총합을 출력하라.
• 조건
  • 우수 마을의 주민 수를 최대화해야 한다.
  • 연결된 두 마을은 모두 선택될 수 없다.
  • 선정되지 못한 마을은 적어도 하나의 우수 마을과 인접해야 한다.

풀이

• 주어진 자료를 트리 형태로 변환한 후 동적 프로그래밍을 활용한다.
• 이때 한 번에 2개의 depth를 가지는 노드 정보가 필요하므로, 인위적으로 rooted Tree 로 변환하여 접근한다.
• 선택한 노드를 기준으로 그 노드 선택 여부에 따른 연산 결과를 노드[0], 노드[1] 로 나누어 dfs를 수행하여 계산 결과인 주민 수의 총 합을 저장한다.
• dfs 과정을 한 번 거치면 루트 노드에서 출발해 리프 노드까지 전체를 돌며 값을 갱신하므로, 루트 노드에 저장된 배열 중에 최대값이 존재하게 된다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const N = Number(input());
  const val = input().split(" ").map(Number);
  let arr = new Array(N + 1),
    linkedList = new Array(N + 1);

  for (let i = 1; i < N; i++) {
    temp = input().split(" ");
    if (!linkedList[temp[0]]) linkedList[temp[0]] = [];
    if (!linkedList[temp[1]]) linkedList[temp[1]] = [];
    linkedList[temp[0]].push(temp[1]);
    linkedList[temp[1]].push(temp[0]);
  }
  for (i = 1; i <= N; i++) arr[i] = new Array(2).fill(0);

  dfs(1, -1);
  console.log(Math.max(...arr[1]));
  process.exit();

  function dfs(node, parent) {
    arr[node][1] = val[node - 1];
    for (const child of linkedList[node]) {
      if (child == parent) continue;
      dfs(child, node);
      arr[node][0] += Math.max(...arr[child]);
      arr[node][1] += arr[child][0];
    }
  }
});