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

문제: www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

 

문제풀이

 

배열 board에서 입력으로 주어진 좌표 범위를 모두 1로 초기화하고 0인 부분을 BFS했다.

 

 

코드

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

using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int visited[100][100] = {0,};
int board[100][100] = {0,};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int m,n,k;
    cin>>m>>n>>k;

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

        for(int i=y1; i<y2; i++){ //주어진 좌표 1로 초기화
            for(int j=x1; j<x2; j++){
                board[i][j] = 1;
            }
        }
    }

    vector<int> varea;
    queue<pair<int,int>> q;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j] || board[i][j]) continue; //방문했거나 board값이 1이면 continue

            q.push({i,j});
            visited[i][j] = 1;
            int area = 0; //영역의 넓이

            while(!q.empty()){
                pair<int,int> cur = q.front();
                q.pop();
                area++;

                for(int dir=0; dir<4; dir++){
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];

                    if(nx<0 || nx>=m || ny<0 || ny>=n) continue;
                    if(visited[nx][ny] || board[nx][ny]) continue;

                    q.push({nx,ny});
                    visited[nx][ny] = 1;
                }
            }
            varea.push_back(area);
        }
    }

    sort(varea.begin(), varea.end()); //영역의 넓이 오름차순 정렬
    
    cout<<varea.size()<<"\n"; //영역의 개수
    for(auto a : varea)
        cout<<a<<" ";

    return 0;
}

 

 

결과