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

문제보기

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const map = input.map((item) => item.split("").map((value) => +value));
const visited = new Array(N).fill(0).map(() => new Array(N).fill(0));
const direction = [
    [-1, 0],
    [0, -1],
    [1, 0],
    [0, 1],
];
let count = [];

const DFS = (col, row) => {
    const stack = [[col, row]];
    let result = 0;
    while (stack.length) {
        let [x, y] = stack.pop();
        if (map[x][y] && !visited[x][y]) {
            result++;
            visited[x][y] = 1;
            for (let i = 0; i < 4; i++) { // 상하좌우로 값이 있는지와 방문하지 않은곳인지 확인
                let [dx, dy] = [x + direction[i][0], y + direction[i][1]];
                if (dx < 0 || dy < 0 || dx >= N || dy >= N) continue;
                if (map[dx][dy] && !visited[dx][dy]) {
                    stack.push([dx, dy]);
                }
            }
        }
    }
    if (result > 0) { // 스택이 다 비워졌을때 result의 값이 있으면 count에 push
        count.push(result);
    }
};

for (let x = 0; x < N; x++) {
    for (let y = 0; y < N; y++) {
        if (map[x][y] && !visited[x][y]) {
            DFS(x, y);
        }
    }
}

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

지도의 크기가 정사각형으로 주어지기 때문에 이중for문으로 모든 영역을 확인한다
확인한 영역에 값이 있고 방문하지 않은곳이면 DFS 함수에 인자로 넘겨준다
DFS 함수가 실행될때마다 result가 카운트되며 stack이 다 비워졌을때 result의 값이 0보다 크면 count 배열에 push 해준다.