[baekjoon] 1068 트리 (Javascript)

1068번: 트리 (acmicpc.net)

1068번: 트리

---

알고리즘 : 트리, dfs

 

리프노드 => dfs를 활용해 풀이

 

let input = require("fs")
  .readFileSync("input.txt") //"/dev/stdin"
  .toString()
  .split("\n")
  .map((val) => val.trim());

let n = +input.shift();
let node = input
  .shift()
  .split(" ")
  .map((v) => +v);
let remove = +input.shift();

let rootNode;
let tree = [];

node.forEach((v, i) => {
  if (v === -1) {
    rootNode = i;
    return;
  }
  if (!tree[v]) tree[v] = [];
  tree[v].push(i);
});

let cnt = 0;
// dfs => 리프노드 수를 구하는 것
const dfs = (root) => {
  if (!tree[root]) {
    cnt++;
    return;
  }
  tree[root].forEach((node) => {
    if (node === remove) {
      if (tree[root].length === 1) cnt++;
      return;
    }
    dfs(node);
  });
};
if (remove === rootNode) {
  console.log(0);
  return;
}
dfs(rootNode);

console.log(cnt);