[백준2583_자바스크립트(javascript)] - 영역 구하기

🔴 문제

영역 구하기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [nmk, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

const [m, n, k] = nmk.split(' ').map((it) => Number(it));
const maps = Array.from({ length: m }, () => Array(n).fill(0));
const crds = inputs.map((it) => it.split(' ').map((it) => Number(it)));

for (const crd of crds) {
  const [x1, y1, x2, y2] = crd;
  for (let i = y1; i < y2; i++) {
    for (let j = x1; j < x2; j++) {
      maps[i][j] = 1;
    }
  }
}

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

const q = [];
function bfs(x, y) {
  q.push([x, y]);
  let area = 1;
  maps[x][y] = 1;

  while (q.length) {
    const [x, y] = q.shift();

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;

      if (maps[nx][ny] === 0) {
        area += 1;
        maps[nx][ny] = 1;
        q.push([nx, ny]);
      }
    }
  }
  return area;
}

const result = [];

for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    if (maps[i][j] == 0) {
      result.push(bfs(i, j));
    }
  }
}

console.log(result.length);
console.log(...result.sort((a, b) => a - b));

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [nmk, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

const [m, n, k] = nmk.split(' ').map((it) => Number(it));
const maps = Array.from({ length: m }, () => Array(n).fill(0));
const crds = inputs.map((it) => it.split(' ').map((it) => Number(it)));

for (const crd of crds) {
  const [x1, y1, x2, y2] = crd;
  for (let i = y1; i < y2; i++) {
    for (let j = x1; j < x2; j++) {
      maps[i][j] = 1;
    }
  }
}

let area = 0;
const result = [];


function dfs(x, y) {
  if (0 <= x && x < m && 0 <= y && y < n) {
    if (maps[x][y] === 0) {
      maps[x][y] = 1; 
      area += 1;
      dfs(x + 1, y);
      dfs(x - 1, y);
      dfs(x, y + 1);
      dfs(x, y - 1);
      return true;
    }
    return false;
  }
}

for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    if (dfs(i, j)) {
      result.push(area);
      area = 0;
    }
  }
}

console.log(result.length);
console.log(...result.sort((a, b) => a - b));

🟢 풀이

bfs/dfs 두가지 방법으로 풀이할 수 있는 문제이다.

입력받은 k줄의 좌표값으로 모눈종이를 만들어준다. 이때 모눈종이의 모양을 실제 모양과 동일하게 만들겠다고 y를 뒤집에서 모눈종이를 칠해주지 않아도 된다. 우리는 영역만 구하면 되니께..

아무튼 bfs로 풀경우 해당 위치가 미방문일 경우 if (maps[i][j] == 0) bfs를 수행한다. bfs를 수행하면서 방문했을 때 해당 위치를 1로 바꾸면서 방문체크해주면 됨

dfs로 풀 경우 해당 위치로 dfs를 수행한 결과값이 true일 경우 (깊이 우선탐색을 마쳐서 방문한 모든곳을 1로 변경하고 난 후 true를 반환할 경우) 결과값을 1 증가시켜주면 된다.

🔵 Ref