[백준 2583] 영역 구하기
January 29, 2023
문제
https://www.acmicpc.net/problem/2583
아이디어
- 먼저 입력 값을 가지고 전체 맵을 나타내는 2차원 배열을 만들어서
직사각형이 그려진 위치에는 1을, 비어있는 위치에는 0을 나타나게끔 했다. -
그 다음에는 모든 좌표를 한번씩 지나가면서 다음과 같은 로직을 수행한다.
- 현재 좌표가 직사각형이 그려진 위치라면 다음 좌표로 스킵한다.
- 현재 좌표가 직사각형이 그려진 위치가 아니라면 큐에 현재 좌표를 넣는다.
-
큐가 비어있게 될 때까지, 꺼내면서 다음을 반복한다. (BFS 탐색)
- 현재 위치가 맵 영역 바깥이거나, 직사각형이 그려진 위치라면 다음 큐 요소로 스킵한다.
- 현재 위치의 상하좌우에 해당하는 위치를 큐에 넣는다.
- 탐색한 노드 갯수를 기록한다.
소스코드
// 입력 정제
const fs = require("fs");
function getInput(caseID) {
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/i${caseID}.txt`;
const input = fs.readFileSync(filePath).toString().split("\n").map(item => item.trim());
input.pop();
const [m, n, k] = input.shift().split(' ').map(item => Number(item));
const map = Array.from({ length: m }, () => Array.from({ length: n }, () => 0) );
for (let i = 0; i < k; i++) {
const [leftX, leftY, rightX, rightY] = input.shift().split(' ').map(item => Number(item));
for (let i = leftY; i < rightY; i++) {
for (let j = leftX; j < rightX; j++) {
map[m - i - 1][j] = 1;
}
}
}
return [m, n, k, map];
}
// 문제
const [m, n, k, map] = getInput(1);
const results = [];
let areaNum = 0;
function isInBoundary(x, y) {
if (x < 0 || x >= n) return false;
if (y < 0 || y >= m) return false;
return true;
}
function solution() {
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (map[i][j]) continue;
// 현재 위치 큐에 넣고 BFS 탐색하기.
let queue = [[i, j]];
let size = 0;
// 주변에 비어있는 공간이 없을 때까지 탐색.
while (queue.length > 0) {
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
const [nowY, nowX] = queue.shift();
// 현재 위치가 비어있는 공간이면, 방문 체크후 주변에 있는 공간 큐에 넣기.
if (isInBoundary(nowX, nowY) && map[nowY][nowX] === 0) {
map[nowY][nowX] = 1;
size++;
for (let k = 0; k < 4; k++) {
const nextX = nowX + dx[k];
const nextY = nowY + dy[k];
queue.push([nextY, nextX]);
}
}
}
// 탐색 끝나면 비어있는 공간 메모.
areaNum++;
results.push(size);
}
}
console.log(areaNum);
console.log(results.sort((a, b) => a - b).join(' '));
}
// 실행
solution();