[JS] 백준 2667번 단지번호붙이기

---

문제 링크

https://www.acmicpc.net/problem/2667

전략

1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
대각선상에 집이 있는 경우는 연결된 것이 아니다.
지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

코드 

DFS를 이용한 풀이 

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

const input = [];
rl.on("line", function (line) {
    input.push(line.split("").map(Number));
}).on("close", function () {
    solution(input);
    process.exit();
});

const solution = (arr) => {
    const n = +arr.shift().join("");

    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    const cnt_arr = [];

    let cnt;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (arr[i][j]) {
                cnt = 0;
                dfs(i, j);
                cnt_arr.push(cnt);
            }
        }
    }

    cnt_arr.sort((a, b) => a - b);
    console.log(cnt_arr.length);
    console.log(cnt_arr.join("\n"));

    function dfs(x, y) {
        if (!arr[x][y]) return;
        arr[x][y] = 0;
        cnt++;
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < n && arr[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }
};

BFS를 이용한 풀이 

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

const input = [];
rl.on("line", function (line) {
    input.push(line.split("").map(Number));
}).on("close", function () {
    solution(input);
    process.exit();
});

const solution = (arr) => {
    const n = +arr.shift().join("");

    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    const cnt_arr = [];

    let cnt;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (arr[i][j]) {
                cnt = 0;
                bfs(i, j);
                cnt_arr.push(cnt);
            }
        }
    }

    cnt_arr.sort((a, b) => a - b);
    console.log(cnt_arr.length);
    console.log(cnt_arr.join("\n"));

    function bfs(x, y) {
        if (!arr[x][y]) return;
        const queue = [];
        arr[x][y] = 0;
        queue.push([x, y]);
        while (queue.length) {
            const [x, y] = queue.shift();
            cnt++;
            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (0 <= nx && nx < n && 0 <= ny && ny < n && arr[nx][ny]) {
                    arr[nx][ny] = 0;
                    queue.push([nx, ny]);
                }
            }
        }
    }
};

 

회고

readline에서 input을 받는 처리가 아직 미숙하다보니 n이 10의 자리수를 넘어가면 문제가 발생하여서 이 문제를 해결하느라 고생했다. 구현은 잘 된 것 같은데 왜 안되는지 이상한데에서 고생하였다. 나름대로 코드를 깔끔하게 구성하려고 노력했다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)