99클럽 코테 스터디 31일차 TIL - 영역 구하기

---

const fs = require('fs');

const data = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [M, N, K] = data[0].split(' ').map(Number);

const rectangles = data.slice(1).map(line => line.split(' ').map(Number));

function findAreasOfSeparatedRegions(M, N, rectangles) {
    let grid = Array.from({ length: M }, () => Array(N).fill(0));

    rectangles.forEach(([x1, y1, x2, y2]) => {
        for (let y = y1; y < y2; y++) {
            for (let x = x1; x < x2; x++) {
                grid[y][x] = 1;
            }
        }
    });

    function bfs(startY, startX) {
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        let queue = [[startY, startX]];
        let area = 0;
        grid[startY][startX] = 2;

        while (queue.length > 0) {
            let [y, x] = queue.shift();
            area++;
            for (let [dy, dx] of directions) {
                let ny = y + dy;
                let nx = x + dx;
                if (ny >= 0 && ny < M && nx >= 0 && nx < N && grid[ny][nx] === 0) {
                    grid[ny][nx] = 2; 
                    queue.push([ny, nx]);
                }
            }
        }
        return area;
    }

    let areas = [];

    for (let y = 0; y < M; y++) {
        for (let x = 0; x < N; x++) {
            if (grid[y][x] === 0) {
                let area = bfs(y, x);
                if (area > 0) {
                    areas.push(area);
                }
            }
        }
    }

    areas.sort((a, b) => a - b);
    return [areas.length, areas];
}

const [numAreas, areas] = findAreasOfSeparatedRegions(M, N, rectangles);

console.log(numAreas);
console.log(areas.join(' '));