[BOJ] #2583 영역 구하기

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

2583번: 영역 구하기

---

입력받은 행렬을 평면좌표 형태로 바꾸어 BFS 순회로 인근 영역의 넓이와 갯수를 구하는 문제이다. 근래에 계속 풀어왔던 문제 형태인지라 어렵지 않게 풀어낼 수 있었다. 다만, 실제로 코테나 시험장에 가서 이정도 난이도의 문제를 마주쳤을때 지금처럼 능숙히 풀어낼 수 있을지는 미지수다. PS는 별 지름길이 따로 없이 그냥 계속 연습하고 꾸준히 풀어보는수 밖에 없는 것 같다.

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

#define MAX 101

using namespace std;

int M,N,K;
int arr[MAX][MAX];
bool visited[MAX][MAX] = { false };

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, 1, -1 };

vector<int> total;

void makeArr(int x, int y) {
    for (int i=0; i<x; i++) {
        for (int j=0; j<y; j++) {
            arr[i][j] = 0;
        }
    }
}
void BFS(int x, int y) {
    queue<pair<int,int>> Q;
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    int cnt=0;
    cnt++;

    while(!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if ((newX>=0 && newX<M) && (newY>=0 && newY<N) && 
            (visited[newX][newY] == false)) {
                if (arr[newX][newY] == 0) {
                    Q.push(make_pair(newX,newY));
                    visited[newX][newY] = true;
                    cnt++;
                }
            }
        }
    }
    total.push_back(cnt);
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> M >> N >> K;

    makeArr(M,N);

    while(K-->0) {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;

        for (int i=x1; i<x2; i++) {
            for (int j=y1; j<y2; j++) {
                arr[j][i] = 1;
            }
        }
    }

    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            if (visited[i][j] == false && arr[i][j] == 0) BFS(i,j);
        }
    }
    sort(total.begin(), total.end());

    // for (int i=0; i<M; i++) {
    //     for (int j=0; j<N; j++) {
    //         cout << arr[i][j] << ' ';
    //     }
    //     cout << endl;
    // }

    cout << total.size() << '\n';
    for (int aa : total) cout << aa << ' ';
    cout << '\n';

    return 0;
}