[C++] 백준 BOJ 2583 영역 구하기

문제링크 : https://noj.am/2583

단순 DFS/BFS 문제이다.

계산하기 편하게 (1,1)~(N,M)의 영역을 사용한다.

초기에 테두리를 방문한 것으로 체크하고 내부를 미방문한 상태로 초기화 시키면 ▣ <- 이런 형태로 만들어진다.

입력된 사각형은 (x1+1, y2+1)~(x2, y2)의 영역으로 방문 체크를 해주는 것으로 구현하였다.

dfs를 실행할 때마다 cnt 변수를 통해 칸을 체크해준다.

// BOJ 2583 영역 구하기
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int cnt = 0;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
vector<vector<bool> > arr;
 
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (!arr[nx][ny]) {
            cnt++;
            arr[nx][ny] = true;
            dfs(nx, ny);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int X, Y, K;
    cin >> Y >> X >> K;
    // true : 방문, false : 미방문
    // 테두리를 방문한 것으로 만들고 내부는 미방문 상태로 초기화
    arr = vector<vector<bool> >(X + 2, vector<bool>(Y + 2, true));
    for (int i = 1; i <= X; i++)
        for (int j = 1; j <= Y; j++)
            arr[i][j] = false;
 
    // 사각형 영역을 방문한 것으로 입력
    for (int i = 1; i <= K; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int x = x1 + 1; x <= x2; x++)
            for (int y = y1 + 1; y <= y2; y++)
                arr[x][y] = true;
    }
 
    // 결과 카운팅
    vector<int> result;
    for (int x = 1; x <= X; x++) {
        for (int y = 1; y <= Y; y++) {
            if (!arr[x][y]) {
                cnt = 1;
                arr[x][y] = true;
                dfs(x, y);
                result.push_back(cnt);
            }
        }
    }
    sort(result.begin(), result.end());
    cout << result.size() << '\n';
    for (int i : result)
        cout << i << ' ';
 
    return 0;
}