[백준 2583 - Node.js] 영역 구하기

🔗 문제 링크

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

2583번: 영역 구하기

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [M, N, K] = input[0].split(' ').map(Number);
const paper = [...Array(M)].map(() => Array(N).fill(false));

for (let i = 1; i <= K; i++) {
  const [x1, y1, x2, y2] = input[i].split(' ').map(Number);
  for (let y = M - y2; y < M - y1; y++) {
    for (let x = x1; x < x2; x++) {
      paper[y][x] = true;
    }
  }
}

const offset = [[0, 1], [1, 0], [-1, 0], [0, -1]];
const dfs = (start) => {
  const stack = [start];
  let count = 0;
  while (stack.length) {
    const [x, y] = stack.pop();
    count++;
    for (let i = 0; i < 4; i++) {
      const nx = x + offset[i][0];
      const ny = y + offset[i][1];
      if (nx >= 0 && nx < M && ny >= 0 && ny < N && !paper[nx][ny]) {
        paper[nx][ny] = true;
        stack.push([nx, ny]);
      }
    }
  }
  return count;
}

const areas = [];
for (let i = 0; i < M; i++) {
  for (let j = 0; j < N; j++) {
    if (!paper[i][j]) {
      paper[i][j] = true;
      areas.push(dfs([i, j, 0]));
    }
  }
}

console.log(areas.length);
console.log(areas.sort((a, b) => a - b).join(' '));

종이의 각 칸 위에 직사각형이 있으면 true, 없으면 false로 초기화 한 후, DFS를 실행하면서 false인 칸들로 구성된 영역의 크기를 반환하도록 하였다. 방문 여부는 별도의 배열을 만들지 않고 paper의 해당 칸을 true로 변경하여 갱신하였다. 최종적으로 DFS의 반환값들을 areas 배열에 담고, areas의 길이와 areas를 오름차순 정렬하여 이어 붙인 값을 출력하였다.