[node.js] 섬의 개수 ( 백준 4963번 )

 

// 백준 4963번 섬의 개수를 풀었습니다.
const readline = require("readline");

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

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

const main = () => {
    const graph = [];
    const visited = [];

    for (let i = 0; i < N; i++) {
        graph[i] = input[i].split(" ").map(Number);
        visited[i] = new Array(M).fill(false);
    }

    const bfs = (yPos, xPos) => {
        const xMove = [0, 0, -1, 1, -1, -1, 1, 1];
        const yMove = [1, -1, 0, 0, 1, -1, 1, -1];
        const queue = [];
        queue.push({ yPos: yPos, xPos: xPos });
        visited[yPos][xPos] = true;

        while (queue.length) {
            const { yPos, xPos } = queue.shift();
            for (let i = 0; i < 8; i++) {
                const nextY = yPos + yMove[i];
                const nextX = xPos + xMove[i];
                if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
                    if (!visited[nextY][nextX] && graph[nextY][nextX]) {
                        visited[nextY][nextX] = true;
                        queue.push({ yPos: nextY, xPos: nextX });
                    }
                }
            }
        }
    };

    let count = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (!visited[i][j] && graph[i][j]) {
                count++;
                bfs(i, j);
            }
        }
    }
    console.log(count);
};

바로 전 문제보다 코드가 더 깔끔해지지 않았나?
이제는 javascript로도 코드를 어느 정도 정립해 가는 거 같다. Cpp보다 코드가 특별히 더 길어지지 않게.

 

 

1년 전에 막 코딩을 처음 시작했을 땐, 알고리즘이 프로그래밍의 전부인 양 공부했다. 그래서 하루 종일 문제만 풀었다.

이 문제도 내가 많이 고전했었던 문제인 거 같다. 그 때는 bfs, dfs가 뭔지도 모르고 이 문제에 도전했으니...

결국 풀기야 풀었는데, 다시 풀려다가 포기했던 문제였던 거 같다.

그런데 언어를 바꾼 지금은, 프로그래밍 경험이 쌓여서인지, 오랜만에 알고리즘을 하는 데도 한 번에 풀었다.

참 기분이 좋아진다.

 

아! 이전에는 dfs로 풀었었는데, 이번에는 bfs로 풀었다.

dfs로 하다가는 javascript에서 스택이 초과될까봐 무섭다. 그래서 dfs는 잘 못하겠다. 원래 dfs를 더 즐겨 사용했는데도.