[boj] 14267. 회사 문화 1 (node.js)

문제 요약

[boj] 14267. 회사 문화 1 (node.js)

풀이

• 알고리즘만 보면 일반적인 bfs, 트리 탐색 문제다. 자료구조를 저장해둔 후, dfs를 통해 하위 노드를 탐색하여 점수를 계산한다.
• 다만, 주어진 점수(간선의 가중치)를 한 줄씩 입력받아 매번 dfs()를 호출해 점수를 누적시키면 시간 초과가 발생한다.
• 시간 초과를 피하기 위해서는 점수를 누적시킨 다음 dfs() 딱 한 스코프만 벗어나서 한 번만 호출해주면 된다. 해당 방법이 가능한지 확인해보면, 먼저 문제에서 루트 노드(1 == 사장)을 이미 알려주었으므로 루트 노드의 호출이 가능하며, 점수는 특정 노드를 기준으로 하위 노드 모두에 누적되어야 하므로, 더하고자 하는 노드에 점수를 누적해두었다가 호출이 가능하다.

내 풀이

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

function solution() {
  const [n, m] = input();
  const arr = input();
  let scores = new Array(n + 1).fill(0);
  let tree = [];
  arr.forEach((elem, idx) => {
    if (idx == 0) return;
    if (!tree[elem]) tree[elem] = [];
    tree[elem].push(idx + 1);
  });
  for (let i = 0; i < m; i++) {
    let [idx, score] = input();
    scores[idx] += score;
  }
  dfs(1);
  scores.splice(0, 1);
  console.log(scores.join(" "));

  function dfs(node) {
    if (!tree[node]) return;
    tree[node].forEach((child) => {
      scores[child] += scores[node];
      dfs(child);
    });
  }
}

let _line = 0;
const input = () => stdin[_line++].split(" ").map(Number);

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});

주절주절

• 얼핏 보면 간단하지만, 결과를 알려주지 않는 코테의 문제였다면 시간복잡도를 잘못 계산해 틀릴 수 있던 문제였다. 사전에 대략적인 시간복잡도라도 무리가 가지 않음을 명확히 파악하자.