[백준] 2583번 영역 구하기

[풀이]

쉬운 문제인데 처음에 좀 헷갈렸습니다..  저 색칠된 부분이 좌표라고 생각했는데 그게 아니어서 당황했던거죠..ㅠ 

그렇지만 주어진 좌표를 토대로 제 입맛에 맞게 (위 그림처럼) 새로운 2D array를 만들고 해결하면 간단하게 풀리는 문제였습니다!

새로운 배열로 비어있는 부분을 BFS 탐색하였습니다.

 

아래는 풀이한 코드입니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int xpos[] = { 0, 1, -1, 0 };
int ypos[] = { 1, 0, 0, -1 };
int map[100][100];
 
int bfs(int x, int y, int m, int n) {
    queue<pair<int, int>> q;
    map[x][y] = 1;
    q.push({ x,y });
    int area = 1;
    while (!q.empty()) {
        pair<int, int> pos = q.front();
        q.pop();
        for (int i = 0; i < sizeof(xpos) / sizeof(int); i++) {
            int next_x = pos.first + xpos[i];
            int next_y = pos.second + ypos[i];
            if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n) {
                if (!map[next_x][next_y]) {
                    area++;
                    map[next_x][next_y] = 1;
                    q.push({ next_x,next_y });
                }
            }
        }
    }
    return area;
}
int main(void) {
    int m, n, k;
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        // 직사각형 입력
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        // x, y를 큰 숫자 쪽에서 1씩 빼주면 
        // 그림과 같은 2D array를 만들수 있다.
        for (int i = x1; i <= x2-1; i++) {
            for (int j = y1; j <= y2-1; j++) {
                map[i][j] = 1;
            }
        }
    }
    vector<int> result;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!map[i][j]) 
                result.push_back(bfs(i, j, m, n));
        }
    }
    sort(result.begin(), result.end());
    cout << result.size() << endl;
    for (auto x : result) cout << x << ' ';
 
    return 0;
}

질문이나 지적사항은 댓글로 부탁드립니다 :)