2583번 영역구하기 - C++

✅️[문제]
https://www.acmicpc.net/source/47203953

로그인

✅️[풀이]

BFS 문제이다.
입력받은 좌표에 대해 arr의 값을 1씩 증가시키고, arr이 0인 것에 대해 BFS를 돌려 횟수를 증가시킨다.

✅️[코드]

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

int dx[4] = {1,0,-1,0};

int dy[4] = {0,1,0,-1};

int main(){

   ios::sync_with_stdio(0);

   cin.tie(0);

   

   int m,n,k;

   

   cin >> m >> n >> k;

   

   int arr[m][n];

   bool vis[m][n];

   

   memset(arr, 0, sizeof(arr));

   memset(vis, 0, sizeof(vis));

   int ans = 0;

   vector<int> V;

   while(k--){

       int x1, y1;

       cin >> x1 >> y1;

       int x2, y2;

       cin >> x2 >> y2;

       

       int x3 = x1;

       int y3 = m - y2;

       for(int i = 0; i< x2-x1; i++){

           for(int j= 0; j<y2-y1; j++){

               arr[y3+j][x3+i]++;

           }

       }

   }

       for(int i=0; i<m; i++){

           for(int j=0; j<n; j++){

               queue<pair<int,int>> q;

               int t2= 0;

               if(!arr[i][j] && !vis[i][j]) {

                   q.push({i,j});

                   vis[i][j] = 1;

                   ans++;

                   t2++;

               }

               while(!q.empty()){

                   auto t = q.front(); q.pop();

                   for(int i=0; i<4; i++){

                       int x = t.X + dx[i];

                       int y = t.Y + dy[i];

                       

                       if(x<0 || x>=m || y<0 || y>=n) continue;

                       if(arr[x][y] || vis[x][y]) continue;

                       

                       t2++;

                       vis[x][y] = 1;

                       q.push({x,y});

                   }

               }

               if(t2 > 0) V.push_back(t2);

           }

       }

   cout << ans << '\n';

   sort(V.begin(), V.end());

   for(int i=0; i<V.size(); i++){

       cout << V[i] << ' ';

   }

}