[node.js] 연결 요소의 개수 ( 백준 11724번 )

kscodebase.tistory.com/394

이전 문제에 JavaScript에 대한 단점들을 조금 나열했는데, 나름대로 깔끔하게 고쳐보고자 이번에는 중첩된 함수 구조를 사용했다.

// 백준 11724번 연결요소의 게수를 풀었습니다.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];
let N = 0;
let M = 0;

rl.on("line", (line) => {
    if (!N) {
        [N, M] = line.split(" ").map(Number);
    } else {
        input.push(line);
        if (input.length === M) {
            main();
            process.exit();
        }
    }
});

const main = () => {
    let visited = new Array(N + 1).fill(false);

    const edge = [];
    for (let i = 1; i <= N; i++) {
        edge[i] = [];
    }

    for (let i = 0; i < M; i++) {
        const [from, to] = input[i].split(" ").map(Number);
        edge[from].push(to);
        edge[to].push(from);
    }

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

        for (let i = 0; i < edge[start].length; i++) {
            const next = edge[start][i];

            if (!visited[next]) {
                dfs(next);
            }
        }
    };

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

    console.log(count);
};

모든 정점이 연결되었다고 적혀 있지 않은 경우에는 이 문제에서 구하라는 것처럼, 분할된 그래프일 수 있다. 연결 그래프가 아닐 수도 있다는 뜻이다.
이 문제는 개념을 알려주고자 하는 간단한 문제였다.