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

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 본 문제는 2006 한국정보올림피아드 지역 본선 고등부 2번 문제다. 빈 공간을 찾고 빈 공간의 개수를 구하는 BFS문제다. 그러나 입력되는 데이터가 배열 index의 순서와 다르기 때문에 입력된 정보를 배열에 맞게 바꿔야 한다. 입력되는 데이터는 왼쪽 아래 꼭짓점의 x, y 좌표값과 오른쪽 위 꼭짓점의 x, y 좌표값이 들어온다. 이 정보를 배열로 바꾸는 것이 문제의 핵심이다.

1. 사각형 개수를 구한다.
2. 사각형의 시작 위치를 구한다.
3. 사각형이 아닌 구역을 구한다.

 

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int v[100][100] = {0};
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool chk[100][100];
 
int main() {
    int n, m, k, a, b, c, d, x, y;
    scanf("%d %d %d", &n, &m, &k);
    for (int t = 0; t < k; t++) {
        scanf("%d %d %d %d", &a, &b, &c, &d);
        x = d - b; // 사각형의 새로 개수
        y = c - a; // 사각형의 가로 개수
        // 사각형 시작 위치 = (b, a);
        for (int i = b; i < b+x; i++) {
            for (int j = a; j < a+y; j++) {
                v[i][j] = 1;
            }
        }
    }
    vector<int> ans;
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (v[i][j] == 0 && !chk[i][j]) {
                q.push(make_pair(i, j));
                chk[i][j] = true;
                int cnt = 0;
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    cnt += 1;
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                            if (v[nx][ny] == 0 && !chk[nx][ny]) {
                                q.push(make_pair(nx, ny));
                                chk[nx][ny] = true;
                            }
                        }
                    }
                }
                ans.push_back(cnt);
            }
        }
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) {
        printf("%d", ans[i]);
        if (i != ans.size()-1) printf(" ");
    }
    return 0;
}