[백준 2583번] 영역 구하기_C++

[백준 2583번 영역 구하기 URL]

[소스 코드]

#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
 
#define MAX 100
 
int N, M, K;
int map[MAX][MAX];
int num[MAX];
bool visited[MAX][MAX];
int dir[4][2] = {
    {0,1}, {0,-1}, {1,0}, {-1,0}
};
 
typedef struct _node {
    int row;
    int col;
    int cnt;
}Node;
 
void SetMap(Node leftDown, Node rightUp) {
 
    for (int i = rightUp.row; i < leftDown.row; i++) {
        for (int j = leftDown.col; j < rightUp.col; j++) {
            map[i][j] = -1;
        }
    }
}
 
bool isBoundary(int row, int col) {
    return (row >= 0 && row < M) && (col >= 0 && col < N);
}
 
void Solve(int r, int c, int cc) {
 
    queue<Node> q;
    q.push(Node{ r, c });
    visited[r][c] = true;
    map[r][c] = cc;
    num[cc] += 1;
 
 
    while (!q.empty()) {
 
        Node node = q.front();
        q.pop();
        int row = node.row;
        int col = node.col;
        int cnt = node.cnt;
 
        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i][0];
            int nc = col + dir[i][1];
            if (isBoundary(nr, nc) && !visited[nr][nc] && map[nr][nc] != -1) {
                visited[nr][nc] = true;
                map[nr][nc] = cnt;
                num[cc] += 1;
                q.push(Node{ nr,nc,cnt });
            }
        }
    }
}
 
int main(void) {
 
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++) {
        int lr, lc, rr, rc;
        cin >> lr >> lc >> rr >> rc;
        Node leftDown = Node{ M - lc,  lr,0 };
        Node rightDown = Node{ M - rc, rr,0 };
        SetMap(leftDown, rightDown);
    }
    int ans = 1;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] != -1 && !visited[i][j]) {
                Solve(i, j, ans);
                ans += 1;
            }
        }
    }
    cout << ans - 1 << endl;
    sort(num+1, num + ans);
    for (int i = 1; i <= ans - 1; i++) {
        cout << num[i] << " ";
    }
    cout << endl;
 
    return 0;
}