코딩테스트(알고리즘)/baekjoon

[baekjoon] 1068 트리 (Javascript)

Cafe Mocha 2023. 1. 27. 10:05

1068번: 트리 (acmicpc.net)

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

알고리즘 : 트리, 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);