백준[2583] - 영역 구하기

문제

백준 2583 문제 보기

접근 방법

map 배열에 먼저 직사각형을 의미하는 좌표를 -1로 저장한다. 이후 map 배열를 검사하면서 직사각형 영역이 아니라면 완전탐색을 실시한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    int x, y, x2, y2;
};

int M, N, K, t;
int map[101][101];
int rr[4] = {1, 0, -1, 0};
int cc[4] = {0, 1, 0, -1};
vector<Point> arr;
vector<int> ans;

int dfs(int r, int c) {
    for(int i = 0; i < 4; i ++) {
        int nextR = r + rr[i];
        int nextC = c + cc[i];
        if(map[nextR][nextC] == 0 && nextR < M && nextC < N && nextC >= 0 && nextR >= 0) {
            t ++;
            map[nextR][nextC] = t;
            dfs(nextR, nextC);
        }
    }
    return 0;
}

int main() {
    cin >> M >> N >> K;
    // 좌표 저장
    for(int i = 0; i < K; i ++) {
        Point p;
        cin >> p.x >> p.y >> p.x2 >> p.y2;
        arr.push_back(p);
    }
    // 저장된 좌표에 따라 지도에 -1로 표시
    for(int cnt = 0; cnt < arr.size(); cnt ++) {
        for(int r = arr[cnt].y; r < arr[cnt].y2; r ++) {
            for(int c = arr[cnt].x; c < arr[cnt].x2; c ++) {
                map[r][c] = -1;
            }
        }
    }
    // -1 영역이외의 공간을 완전 탐색
    for(int r = 0; r < M; r ++) {
        for(int c = 0; c < N; c ++) {
            if(map[r][c] == 0) {
                t = 1;
                map[r][c] = t;
                dfs(r, c);
                ans.push_back(t);
            }
        }
    }
    // 오름차순으로 정렬
    sort(ans.begin(), ans.end());

    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i ++) {
        cout << ans[i] << " ";
    }

    return 0;
}