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

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let ans = 0;
let n = Number(input[0]);
let board = new Array(n);
for (let i = 0; i < board.length; i++) {
  board[i] = input[i + 1].split("").map(Number);
}
let visit = new Array(n);
for (let i = 0; i < visit.length; i++) {
  visit[i] = new Array(n).fill(0);
}
let cnt_ans = [];
function BFS(x, y) {
  let cnt = 1;
  let queue = [];
  let dx = [0, 0, 1, -1];
  let dy = [1, -1, 0, 0];
  queue.push([x, y]);
  visit[x][y] = 1;
  while (queue.length) {
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let x = queue.shift();
      for (let j = 0; j < 4; j++) {
        let nx = x[0] + dx[j];
        let ny = x[1] + dy[j];
        if (
          nx >= 0 &&
          nx < n &&
          ny >= 0 &&
          ny < n &&
          board[nx][ny] === 1 &&
          visit[nx][ny] === 0
        ) {
          visit[nx][ny] = 1;
          queue.push([nx, ny]);
          cnt++;
        }
      }
    }
  }
  cnt_ans.push(cnt);
}

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (board[i][j] === 1 && visit[i][j] === 0) {
      BFS(i, j);
    }
  }
}
console.log(cnt_ans.length);
cnt_ans.sort((a, b) => a - b);
for (let i = 0; i < cnt_ans.length; i++) {
  console.log(cnt_ans[i]);
}

✔ 알고리즘 : BFS

✔ BFS함수를 실행한 횟수가 구역의 수

✔ 방문체크를 위한 배열을 선언하고 board[i][j]가 1인데 방문처리가 안된집에서 부터 BFS탐색을 시작

✔ 구역안에서 queue에 push할때마다 집이 하나씩 증가하므로 cnt++ 해주고 BFS함수가 끝나기 전에 cnt를 ans_cnt에 push한다

✔ 구역의 개수는 ans_cnt.length

✔ 각 구역별 집의 수를 오름차순 정렬하여 출력

✔ 난이도 : 백준 기준 실버 1