BOJ 2583 c++ 영역 구하기

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

 

이 문제를 풀때,  문제에서 주어지는 m이 무엇인지, n이 무엇인지 등을 생각해보면서 일반적으로 풀어왔던 m , n 에 해당하는 column과 row가 맞는지 등을 고려해서 코드를 짜야했다. 그동안 컴퓨터에 입력을 할때 할당하던 형태로 column과 row를 두려면 입력을 받은 값들을 어디에 넣어주어야 할지 잘 생각해보도록 하자. 

 

main 함수에 필요한 연산들을 모두 넣는 형태로 코드를 작성했기 때문에 가독성이 좋지 않은듯한 느낌이 든다. 아직까지는 알고리즘 문제를 푸는데 함수를 따로 선언하고 해당 함수를 main에서 사용하는 형태의 코드를 짜오지 않아서 아래와 같은 형태로 주로 코드를 작성하지만, 프로그래머스에서 문제를 풀때는 solution 함수에서 return 값으로 원하는 값들을 내보내는 형태로 코드를 작성해야 하기 때문에, 백준에서 문제를 풀때도 그러한 형태로 함수들을 선언하고 main에서 불러들이는 식으로 한번 작성해보도록 하자. 

 

// 주어지는 4자리 좌표를 통해서 해당 보드에 1을 입히는 방식으로 구현하면 될것같다. 

#include <bits/stdc++.h>
using namespace std;
//이 문제에서는 m이 row를, n이 column을 의미한다. 주의
//그래서 오히려 내가 반대로 받는게 나을것 같다. 

int board[105][105];//모든 보드를 1로 채워놓고, 그 뒤에 좌표값을 받아서 해당 좌표값들의 위치를 0 으로 초기화 하는 방향으로 가자 

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

int m, n, k;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m>>k;
  
  //모든 보드 1로 초기화. 주어지는 좌표로 0으로 부분 채울 예정
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      board[i][j]=1;
    }
  }
  while(k--){
    int x1,y1,x2,y2;
    cin>>y1>>x1>>y2>>x2;
    for(int i=x1; i<x2; i++){
      for(int j=y1; j<y2; j++){
        board[i][j]=0;
      }
    }
  }
  // for(int i=0; i<n; i++){
  //   for(int j=0; j<m; j++){
  //     cout<<board[i][j]<<' ';
  //   }
  //   cout<<'\n';
  // }
  queue<pair<int,int>> Q;
  vector<int> V;
  int cnt=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(vis[i][j]==1) continue;
      if(board[i][j]==0) continue;
      vis[i][j]=1;
      Q.push({i,j});
      cnt++;
      int area=1;
      // cout<<"h1"<<' ';
      while(!Q.empty()){
        // cout<<"h2"<<' ';
        auto cur= Q.front(); Q.pop();
        for(int dir=0; dir<4; dir++){
          int nx=cur.first+dx[dir];
          int ny=cur.second+dy[dir];
          if(nx<0||nx>=n||ny<0||ny>=m) continue;
          if(vis[nx][ny]==1) continue;
          if(board[nx][ny]==0) continue;
          vis[nx][ny]=1;
          Q.push({nx,ny});
          area++;
          // cout<<"h"<<' ';
        }
      }
      V.emplace_back(area);
    }
  }
  sort(V.begin(),V.end());
  cout<<cnt<<'\n';
  for(auto c:V){
    cout<<c<<' ';
  }
}