백준 1068 JS 풀이

구하는 값

노드를 삭제했을때 남은 트리 중 리프노드 개수

핵심 아이디어

dfs로 리프노드 카운팅 방법

1. 삭제하는 노드의 부모에서 삭제하는 노드를 제거
2. 삭제하는 노드에서 dfs로 자손들을 모두 방문처리함
3. 루트노드에서 dfs를 돌며 더이살 갈 곳이없는 노드(graph[idx].length === 0)를 카운팅

코드

const input = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");

const n = Number(input[0]);
const line = input[1].split(" ").map(Number);
const graph = Array.from({ length: n }, () => []);
let root = 0;
line.forEach((v, i) => {
    if (v !== -1) {
        graph[v].push(i);
    } else root = i;
});
// console.log(graph);

const visited = new Array(n).fill(false);

const dfs = (cur) => {
    visited[cur] = true;

    for (const next of graph[cur]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
};

const delNoot = Number(input[2]);
if (delNoot !== root)
    graph[line[delNoot]] = graph[line[delNoot]].filter((v) => v !== delNoot);
dfs(delNoot);

let leaf = 0;
const dfs2 = (cur, d) => {
    visited[cur] = true;

    if (graph[cur].length === 0) leaf++;

    for (const next of graph[cur]) {
        if (!visited[next]) {
            dfs2(next, d + 1);
        }
    }
};

if (!visited[root]) dfs2(root, 0);

console.log(leaf);

코드가 좀 더럽다… 다른사람 풀이를 보자

다른사람풀이에서 리프노드를 구하는 방식은

먼저 tree를 자식노드가 있는 노드만 만든 후

dfs를돌며

1. root노드와 제거 노드가 같을때는 return 0
2. tree[현재노드]가 없으면 리프노드++
3. 루트노드에서 dfs를 돌며 다음 방문노드가 제거노드일 경우 리프노드++

하는 방식으로 리프노드를 구했다.

다른사람 코드

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);
});

// console.log("tree", tree);
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));

시간은 비슷하게 나오지만 다른사람풀이가 더 가독성이 좋아보인다(반성!)