백준 2667 단지번호붙이기

문제

제한사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let n = +input.shift('');
let arr = input.map((e) => e.split('').map(Number));

const solution = (n, arr) => {
  let townNumber = 0;
  let tmp = [];
  let dx = [1, 0, -1, 0];
  let dy = [0, 1, 0, -1];
  let map = [...arr];

  const bfs = (i, j) => {
    let cnt = 1;
    let queue = [];
    queue.push([i, j]);
    while (queue.length) {
      let [x, y] = queue.shift();
      for (let i = 0; i < dx.length; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny]) {
          map[nx][ny] = 0;
          queue.push([nx, ny]);
          cnt++;
        }
      }
    }
    tmp.push(cnt);
  };

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (map[i][j]) {
        map[i][j] = 0;
        bfs(i, j);
        townNumber++;
      }
    }
  }

  let answer = [townNumber, ...tmp.sort((a, b) => a - b)];
  return answer.join('\n');
};

console.log(solution(n, arr));

• 마찬가지로 섬의 개수와 비슷한 유형의 문제이다.
• 마을 수는 섬의 개수와 같은 원리이다.
• 아파트 수는 bfs 내부에서 count해야한다.