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