[boj] 1068. 트리 (node.js)

문제 요약

[boj] 1068. 트리 (node.js)

• 입력: 트리의 노드의 개수 N, 0 ~ N-1번 노드의 부모 노드의 번호, 삭제할 노드 번호가 주어진다.
• 출력: 리프 노드의 개수를 출력하라.
• 부모가 -1이면 루트 노드이다.

풀이

• 트리 탐색 후 리프노드의 개수를 센다.
• 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 = input();
  const arr = input().split(" ").map(Number);
  const erase = input();
  let tree = [];
  let root = 0;
  let cnt = 0;
  arr.forEach((elem, idx) => {
    if (elem == -1) {
      root = idx;
      return;
    }
    if (!tree[elem]) tree[elem] = [];
    tree[elem].push(idx);
  });

  const result = dfs(root);
  console.log(result);
  process.exit();

  function dfs(node) {
    if (root == erase) return 0;
    if (!tree[node]) {
      cnt++;
      return;
    }
    tree[node].forEach((elem) => {
      if (elem == erase) {
        if (tree[node].length == 1) cnt++;
        return;
      }
      dfs(elem);
    });
    return cnt;
  }
});

• dfs 함수에서의 처리가 핵심이다.
  • root 노드에서부터 시작하므로
  • root == erase 인 경우 리프는 0개
  • root 노드가 삭제 노드가 아닌 경우는 이제 모두 for문 내에서 처리된다.
  • 자식 노드가 삭제 노드인 경우 그 부모 노드가 자식이 더 이상 없을 때만 리프 노드가 된다.
  • 그렇지 않을 경우는 모두 !tree[node] 조건에서 처리된다.