🎲 백준 2583번 영역 구하기

백준 2583번

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [M, N, K] = input.shift().split(" ").map(Number);

let arr = Array.from(new Array(M), () => new Array(N).fill(0));
for (let i = 0; i < K; i++) {
  const [lx, ly, rx, ry] = input[i].split(" ").map(Number);

  for (let y = 0; y < ry - ly; y++) {
    for (let x = 0; x < rx - lx; x++) {
      arr[ly + y][lx + x] = 1;
    }
  }
}

const dir = [
  [0, 1],
  [0, -1],
  [-1, 0],
  [1, 0],
];

const DFS = (j, i) => {
  const willCheck = [[j, i]];
  let count = 1;

  while (willCheck.length) {
    const [pointX, pointY] = willCheck.pop();

    for (let i = 0; i < 4; i++) {
      const nextX = pointX + dir[i][0];
      const nextY = pointY + dir[i][1];

      if (
        nextX >= 0 &&
        nextX < N &&
        nextY >= 0 &&
        nextY < M &&
        arr[nextY][nextX] === 0
      ) {
        willCheck.push([nextX, nextY]);
        count++;
        arr[nextY][nextX] = -1;
    
      }
    }
  }
  return count;
};

const result = [];
for (let i = 0; i < M; i++) {
  for (let j = 0; j < N; j++) {
    if (arr[i][j] === 0) {
      arr[i][j] = -1;
      const count = DFS(j, i);
      result.push(count);
    }
  }
}
console.log(result.length);
console.log(result.sort((a, b) => a - b).join(" "));