kakasoo

[node.js] 단지번호붙이기 ( 백준 2667번 ) 본문

프로그래밍/알고리즘 풀이

[node.js] 단지번호붙이기 ( 백준 2667번 )

카카수(kakasoo) 2021. 4. 10. 13:55
반응형
const readline = require("readline");

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

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

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

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

    const bfs = (yPos, xPos) => {
        let cnt = 1;
        const queue = [];
        const xMove = [0, 0, -1, 1];
        const yMove = [1, -1, 0, 0];

        visited[yPos][xPos] = true;
        queue.push({ yPos: yPos, xPos: xPos });

        while (queue.length) {
            const { yPos, xPos } = queue.shift();

            for (let i = 0; i < 4; i++) {
                const nextY = yPos + yMove[i];
                const nextX = xPos + xMove[i];

                if (
                    nextY >= 0 &&
                    nextY < count &&
                    nextX >= 0 &&
                    nextX < count
                ) {
                    if (graph[nextY][nextX] && !visited[nextY][nextX]) {
                        visited[nextY][nextX] = true;
                        queue.push({ yPos: nextY, xPos: nextX });
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    };

    const answer = [];
    let cnt = 0;
    for (let i = 0; i < count; i++) {
        for (let j = 0; j < count; j++) {
            if (graph[i][j] && visited[i][j] === false) {
                answer.push(bfs(i, j));
                cnt++;
            }
        }
    }

    console.log(cnt);
    answer
        .sort((a, b) => a - b)
        .forEach((el) => {
            console.log(el);
        });
};

한국인이라면 말을 끝까지 듣도록 하자. 내가 이걸 3번째에 맞췄는데, 그 이유는
첫째로 숫자 cnt만 출력했다. 그러니깐 단지 수만 출력해서 틀렸다.
두번째는 오름차순으로 정리를 안해서 틀렸다...
C++에 비해서 코드가 상당히 길긴 하지만, 그렇다고 해서 막 큰 차이가 나지는 않는다.
30~40줄 더 길 수도 있긴 한데, 코드 가독성 자체는 더 좋지 않을까 싶다... ( 라고 JS가 말한다. )

반응형