[백준] 1068 트리 (Javascript)

문제

BOJ1068_트리

풀이

요구사항

트리에서 특정 노드를 잘랐을 때, 리프 노드의 개수를 구하라

해결방안

1. 노드를 자르는 것을 어떻게 구현할 수 있을까?
2. 리프 노드의 개수는 어떻게 구할 수 있을까?

입력값으로 부모 노드의 번호가 주어진다.
노드를 잘랐다는 것은 해당 노드는 부모가 없음을 의미한다.
따라서 자른 노드의 부모노드 번호는 부모가 존재하지 않다는 의미로 -2로 한다. (-1로 하면 루트노드의 부모노드 번호와 겹치기 때문에 -2로 해주었다.)

또한 하나의 노드가 잘리면 그 자식노드도 모두 트리에서 제거되기 때문에 자식 노드들도 부모 노드의 번호를 -2로 바꿔준다. 이는 DFS로 구현해줄 수 있다.

function dfs(num) {
    parent[num] = -2;
    for (let i = 0; i < N; i++) {
        if (num === parent[i]) {
            dfs(i);
        }
    }
}

dfs가 종료되고 나면 트리에서 잘려나간 노드들은 부모 노드가 -2로 설정되어 있고 해당 노드들은 리프 노드가 될 수 없다.

또한 만약 i가 parent 배열에 포함되어 있다면 i는 누군가의 부모 노드라는 뜻이므로, 이러한 경우에도 리프 노드가 될 수 없다.

따라서 parent 배열에 포함되어 있지 않고, 부모 노드가 -2가 아닌 노드의 개수를 세어주면 리프 노드의 개수를 구할 수 있다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const parent = input[1].split(' ').map(Number);
const cut = +input[2];
let count = 0;

function dfs(num) {
    parent[num] = -2;
    for (let i = 0; i < N; i++) {
        if (num === parent[i]) {
            dfs(i);
        }
    }
}

dfs(cut);
for (let i = 0; i < N; i++) {
    if (parent[i] !== -2 && !parent.includes(i)) count++;
}
console.log(count);