문제

  • 침수되는 구역을 기준으로 안전한 영역을 찾는 문제이다.

입력

  • 첫째 줄에 정사각형의 길이가 주어진다. 길이는 2이상 100이하의 정수이다. 둘째 줄부터 N개의 줄에 구역의 높이 정보가 주어진다. 높이는 1이상 100이하의 정수이다.

출력

예제 입력
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7
예제 출력
5

접근

  • 구역, 영역 찾는 문제면 당연히 BFS겠지?

내가 생각한 풀이

  • 따로 기준을 세울 수 있는 것이 없으니 영역이 가장 많아지는 지점을 찾으려면 모든 높이를 다 확인해야 된다고 생각했음.
    • 이때 내가 확인해야 할 것은 주어진 값중 최소값부터 최대값까지임!
  • 비가 내리는 양에 따라 침수되는 부분과 되지 않는 부분으로 구분한 후 BFS를 실행한다.
  • 이 때 비가 안 내릴수도 있다는 가정하에 max의 초기값은 1로 설정한다.

코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int check[101][101] = {0, }, map[101][101] = {0, }, d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}, r[10001] = {0, }, cnt = 0;

bool chk(int a, int b){if(a>=0 && b>=0 && a<100 && b<100) return 1; else return 0;}
struct xy{
  int y;
  int x;
};
void doBFS(int y, int x){
  int numcount = 0;
  queue<struct xy> q;
  check[y][x] = 1;
  q.push({y,x});
  while(!q.empty()){
    struct xy temp = q.front();
    q.pop();
    for(int i = 0 ;i<4;i++){
      if(map[temp.y + d[i][0]][temp.x + d[i][1]] == 2 && chk(temp.y + d[i][0],temp.x + d[i][1]) && check[temp.y + d[i][0]][temp.x + d[i][1]] == 0){//map이 2이고, 0보다 크고 100보다 작은 범위에서, 아직 방문을 안 했을 경우
        q.push({temp.y + d[i][0], temp.x + d[i][1]});
        check[temp.y + d[i][0]][temp.x + d[i][1]] = 1;
      }
    }
    numcount++;
  }
  r[cnt] = numcount;
}

int main(void){
  int m, n, k;
  cin>>m>>n>>k;
  for(int i = 0 ;i<m;i++){
    for(int j = 0 ;j<n;j++)
      map[i][j] = 2;
  }
  for(int i = 0 ;i<k;i++){
    int lx, ly, rx, ry;
    cin>>lx>>ly>>rx>>ry;
    for(int j = ly ;j<ry;j++){//직사각형의 꼭지점의 좌표를 받은 후 영역을 1로 바꿔주는 과정
      for(int k = lx ;k<rx;k++){
        map[j][k] = 1;
        check[j][k] = 1; //직사각형 내부는 확인하지 않을 것이므로 check를 1로 바꿔준다.
      }
    }
  }
  for(int i = 0 ;i<m;i++){
    for(int j = 0 ;j<n;j++){
      if(check[i][j] == 0){//2차원 배열의 모든 부분을 순회하며 방문을 하지 않은 점에 대해서는 BFS를 실행해준다.
        doBFS(i,j);
        cnt++;
      }
      else continue;
    }
  }
  sort(r,r+cnt);
  cout<<cnt<<endl;
  for(int i = 0 ;i<cnt;i++) cout<<r[i]<<" ";
  return 0;
}