2583. 영역 구하기 (C++)

www.acmicpc.net/problem/2583

2583번: 영역 구하기

전형적인 BFS구현 문제였다.

 

문제를 한줄로 요약하자면 이거다.

모눈종이에 직사각형이 그려진다. 그려진 직사각형 이외에 박스들이 몇개, 크기가 어떤지를 출력하면 되는 문제다.

각 배열을 돌아가며 그려진 직사각형 이외에 곳을 발견하면 박스 카운트를 추가하고 BFS를 돌리며 크기를 잰다.

 

아, 그리고 입력에 각 왼쪽 아래 꼭짓점 좌표와 오른쪽 위 꼭짓점 좌표를 주는데, 그 좌표를 이용하여 배열에서 직사각형을 표현하면 된다. (사실 난 이거 어떻게 해야할지 몰라서 몇일 고민했다)(수학을 못하면 이렇게 된다)

 

코드를 보면 이해가 갈것이다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define endl '\n'
int board[100][100];
bool dist[100][100];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int m,n,k;
vector<int> v;
queue<pair<int,int>> Q;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(dist,false,sizeof(dist));
    int x1,y1,x2,y2;
    cin >> m >> n >> k;
    for(int i = 0; i < k; i++) {
        cin >> x1 >> y1 >> x2 >> y2;

        for(int j = x1; j < x2; j++) {
            for(int p = y1; p < y2; p++) {
                board[p][j] = 1;
            }
        }
    }
    int cnt = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(board[i][j] == 1 || dist[i][j]) continue;
            cnt++;
            dist[i][j] = 1;
            int num = 0;
            Q.push({i,j});
            while(!Q.empty()) {
                num++;
                auto cur = Q.front(); Q.pop();
                for(int dir = 0; dir < 4; dir++) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if(dist[nx][ny] || board[nx][ny] == 1) continue;
                    dist[nx][ny] = 1;
                    Q.push({nx,ny});
                }
            }
            v.push_back(num);
        }
    }
    

    cout << cnt << endl;
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++) {
        cout << v[i];
        if(i + 1 == v.size()) {
            break;
        } else {
            cout << ' ';
        }
    }
}

사실 BFS 구현 코드를 함수로 빼서 제작해야 객체지향에 어울리는 코드이지만, 본인은 지금 이 코드가 돌아가는게 더 급선무였기에 이렇게 작성한 걸 이해해주길 바란다. 

 

문제에서 각 박스들의 크기를 오름차순으로 정렬하여 출력하라고 나와있어서, 벡터를 이용해 크기들을 받고, sort 함수를 사용하였다.

 

그리고 출력하면 끝!