[백준] 1068 트리 - javascript

📌 문제

https://www.acmicpc.net/problem/1068

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

input.shift();
const parentInfo = input.shift().split(' ').map(Number);
const eraseNode = +input.shift();

let tree = [];
let cnt = 0;
let rootNode;

parentInfo.forEach((parentNode, idx) => {
  if (parentNode == -1) {
    rootNode = idx;
    return;
  }
  if (!tree[parentNode]) tree[parentNode] = [];
  tree[parentNode].push(idx);
});

const dfs = (node) => {
  if (rootNode == eraseNode) return 0;
  if (!tree[node]) {
    cnt++;
    return;
  }
  tree[node].forEach((nodeNum) => {
    if (nodeNum === eraseNode) {
      if (tree[node].length === 1) cnt++;
      return;
    }
    dfs(nodeNum);
  });
  return cnt;
};

console.log(dfs(rootNode));

✔ 알고리즘 : DFS

✔ tree[parentNode] 의 원소는 부모의 노드번호가 parentNode인 노드이다.

✔ 루트 노드 부터 dfs 탐색을 하면서 리프노드인 경우 cnt를 증가시킨다. 현재 node를 부모로 갖는 노드가 없다면 리프노드이다.

if (!tree[node]) {
  cnt++;
  return;
}

✔ 자식 노드가 삭제 노드인 경우 그 부모 노드가 자식이 더 이상 없을 때만 리프 노드가 된다.

if (tree[node].length === 1) cnt++;

✔ 난이도 : 백준 기준 골드 5