[백준/c++] 2583번: 영역 구하기

 

 

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

2583번: 영역 구하기

 

 

평범한 BFS 문제였다.

그런데 문제는... 지금까지 배열을 왼쪽 상단 == (0,0) 오른쪽 하단 == (N, M) 이런 식으로 진행했는데 여기서는 다르게 나온다.

 

 

 

위의 그림처럼 왼쪽 하단이 (0,0)이고 오른쪽 상단이 (N, M)이다. 그래서 눈금을 그리는 데 있어서 헷갈릴 수 있다.

문제를 대충보면 또 실수를 마구마구 할 수 있다.

문제 제대로 읽고.. 혹시 모르니 꼭 눈금을 제대로 칠했는지 중간에 출력해서 확인해주면 빠르게 풀 수 있을 것이다. >0<

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m, k, arr[101][101];
bool visit[101][101];
queue<pair<int, int>> q;
vector<int> cnt;
int dir[4][2] = {{1, 0}, {0, 1}, {-1,0}, {0,-1}};

int BFS(int a, int b){
    int blank = 1;
    q.push({a, b});
    visit[a][b] = true;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(0<=dx&&dx<m&&0<=dy&&dy<n && !visit[dx][dy] && arr[dx][dy] != 1){
                q.push({dx, dy});
                blank++;
                visit[dx][dy] = true;
            }
        }
    }
    return blank;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n >> k;
    for(int i=0; i<m; i++) for(int j=0; j<n; j++) arr[i][j] = 0; //초기화
    
    for(int i=0; i<k; i++){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int tmp = x1;
        x1 = m - y1;
        y1 = tmp;
        tmp = x2;
        x2 = m - y2;
        y2 = tmp;
        for(int i=x2; i<x1; i++) for(int j=y1; j<y2; j++) arr[i][j] = 1;
    }

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(!visit[i][j] && arr[i][j] != 1){
                int x = BFS(i, j);
                cnt.push_back(x);
            }
        }
    }
    cout << cnt.size() << '\n';
    sort(cnt.begin(), cnt.end());
    for(auto i: cnt) cout << i << ' ';
    cout << '\n';
    return 0;
}