[백준/C++] 영역 구하기_2583

📝 문제

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

💻 코드

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


using namespace std;

int m, n, k;
int MAP[101][101];
int cnt = 0;

struct Node {
    int row;
    int col;
};

int bfs(int row, int col) {
    int dr[] = { 0, 0, 1, -1 };
    int dc[] = { 1, -1, 0, 0 };
    int total = 1;
    queue<Node> q;
    q.push({ row, col });

    while (!q.empty()) {
        Node now = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextRow = now.row + dr[i];
            int nextCol = now.col + dc[i];
            if (nextRow < 0 || nextCol < 0 || nextRow >= m || nextCol >= n) continue;
            if (MAP[nextRow][nextCol] != 0) continue;

            total += 1;
            MAP[nextRow][nextCol] = -1;
            q.push({ nextRow, nextCol });
        }
    }
    

    return total;
}

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

    
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++) {
        int sx, ex, sy, ey;
        cin >> sy >> sx >> ey >> ex;
        for (int x = sx; x < ex; x++) {
            for (int y = sy; y < ey; y++) {
                MAP[x][y] += 1;
            }
        }
    }

    vector<int> v;
    for (int x = 0; x < m; x++) {
        for (int y = 0; y < n; y++) {
            if (MAP[x][y] == 0) {
                MAP[x][y] = -1; // check
                cnt += 1;
                int base = bfs(x, y);
                v.push_back(base);
            }
        }
    }

    sort(v.begin(), v.end());
    cout << cnt << '\n';
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }


    return 0;
}

📌 해결방법

1. 2차원 배열의 시작이 왼쪽 아래라서 어떻게 해야할지 감을 못 잡아서 그냥 왼쪽 위가 (0,0)이라고 생각하고 직사각형을 그려줬다
2. 직사각형이 아닌 모눈종이를 찾고 bfs/dfs를 활용해 연결된 모눈종이를 다 카운트 해준다.

✔ 느낀 점

왼쪽 아래가 (0,0)일 때 어떻게 풀어야 좋을지 모르겠다. 그냥 뒤집어서 풀어도 맞을까,,,