[백준] 4803_트리 (Javascript)

문제

BOJ4803_트리

풀이

DFS로 연결된 그래프를 탐색하면서 방문했던 곳을 또다시 방문했을 때 사이클 발생 여부를 확인하여 사이클이 발생한다면 트리가 아니므로 카운트 하지 않고, 사이클이 발생하지 않았다면 트리이므로 카운트를 증가시키면 된다.

시행착오 1

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
let [N, M] = input[0].split(' ').map(Number);
let t = 1;
let inputIdx = 1;
let answer = '';

while (N !== 0 && M !== 0) {
    const graph = Array.from({ length: N + 1 }, () => []);
    const visited = Array(N + 1).fill(false);
    const arr = input.slice(inputIdx, inputIdx + M).map((e) => e.split(' ').map(Number));

    arr.forEach(([s, e]) => {
        graph[s].push(e);
        graph[e].push(s);
    });

    let count = 0;
    for (let i = 1; i <= N; i++) {
        if (!visited[i]) {
            if (!dfs(i, i)) count++;
        }
    }

    answer += count > 1 ? `Case ${t++}: A forest of ${count} trees.\n` : count === 1 ? `Case ${t++}: There is one tree.\n` : `Case ${t++}: No trees.\n`;
    inputIdx += M;
    [N, M] = input[inputIdx++].split(' ').map(Number);

    function dfs(cur, parent) {
        visited[cur] = true;
        let cycle = false;
        for (let next of graph[cur]) {
            if (!visited[next]) {
                cycle = dfs(next, cur);
            } else if (parent !== next) cycle = true;
        }
        return cycle;
    }
}

console.log(answer.trimEnd());

반례

input
2 0
0 0

answer
Case 1: A forest of 2 trees.

wrong output

원인

테스트 케이스를 반복하는 while문이 문제였다. 노드나 간선의 개수 둘 중 하나라도 0일 경우 while문이 실행이 안되면서 결과가 아무것도 출력되지 않았다.

해결

while 문을 아래와 같이 바꿔주었다.

while (N + M > 0)

시행착오 2

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
let [N, M] = input[0].split(' ').map(Number);
let t = 1;
let inputIdx = 1;
let answer = '';

while (N + M > 0) {
    const graph = Array.from({ length: N + 1 }, () => []);
    const visited = Array(N + 1).fill(false);
    const arr = input.slice(inputIdx, inputIdx + M).map((e) => e.split(' ').map(Number));

    arr.forEach(([s, e]) => {
        graph[s].push(e);
        graph[e].push(s);
    });

    let count = 0;
    for (let i = 1; i <= N; i++) {
        if (!visited[i]) {
            if (!dfs(i, i)) count++;
        }
    }

    answer += count > 1 ? `Case ${t++}: A forest of ${count} trees.\n` : count === 1 ? `Case ${t++}: There is one tree.\n` : `Case ${t++}: No trees.\n`;
    inputIdx += M;
    [N, M] = input[inputIdx++].split(' ').map(Number);

    function dfs(cur, parent) {
        visited[cur] = true;
        let cycle = false;
        for (let next of graph[cur]) {
            if (!visited[next]) {
                cycle = dfs(next, cur);
            } else if (parent !== next) return true;
        }
        return cycle;
    }
}

console.log(answer.trimEnd());

반례

input
6 6
1 2
2 3
3 4
4 2
3 5
1 6
0 0

answer
Case 1: No Trees.

wrong output
Case 1: There is one tree.

원인

DFS를 수행하며 사이클이 발생할 경우 cycle 변수에 true가 저장되는데 이 상태로 함수를 종료시키지 않아서, 다른 노드에서 사이클이 발생하지 않고 종료되어 false를 반환하며 cycle의 값이 false로 덮어씌어져서 사이클이 발생하지 않은 것으로 여기고 카운트를 증가시켜서 발생한 문제다.

해결

코드를 수정하여, 사이클이 발생했다면 더 이상 탐색하지 않고 종료하도록 수정했다.

if (dfs(next, cur)) return true;

최종 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
let [N, M] = input[0].split(' ').map(Number);
let t = 1;
let inputIdx = 1;
let answer = '';

while (N + M > 0) {
    const graph = Array.from({ length: N + 1 }, () => []);
    const visited = Array(N + 1).fill(false);
    const arr = input.slice(inputIdx, inputIdx + M).map((e) => e.split(' ').map(Number));

    arr.forEach(([s, e]) => {
        graph[s].push(e);
        graph[e].push(s);
    });

    let count = 0;
    for (let i = 1; i <= N; i++) {
        if (!visited[i]) {
            if (!dfs(i, i)) count++;
        }
    }

    answer += count > 1 ? `Case ${t++}: A forest of ${count} trees.\n` : count === 1 ? `Case ${t++}: There is one tree.\n` : `Case ${t++}: No trees.\n`;

    inputIdx += M;
    [N, M] = input[inputIdx++].split(' ').map(Number);

    function dfs(cur, parent) {
        visited[cur] = true;
        for (let next of graph[cur]) {
            if (!visited[next]) {
                // 사이클이 발생했으면 더 이상 탐색하지 않고 종료
                if (dfs(next, cur)) return true;
            }
            // 방문한 적 있고, 직전 노드가 아니라면 사이클 발생
            else if (parent !== next) return true;
        }
        return false;
    }
}

console.log(answer.trimEnd());