BOJ 2583 영역 구하기 DFS

- Y 좌표가 뒤집어져 있어서 input 할 때 헷갈렸다.

- DFS, recursion으로 해결

- 영역 갯수, 영역 크기 모두 구해야 한다.

 

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

 

#include <cstdio>
#include <algorithm>
using namespace std;

int board[110][110];
int visited[110][110];
int ans[110*110];

int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
int m, n, k;

void dfs(int x, int y, int cnt){
  visited[x][y]=cnt; //영역번호.
  for(int i=0; i<4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx>=0 && nx<m && ny>=0 && ny<n){
      if(board[nx][ny]==0 && visited[nx][ny]==0){
        dfs(nx, ny, cnt);
      }
    }
  }
}

int main(){
  scanf("%d %d %d", &m, &n, &k);

  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      board[i][j]=0;
      visited[i][j]=0;
    }
  }

  while(k--){
    int inputX, inputY, inputX2, inputY2;
    scanf("%d %d %d %d", &inputX, &inputY, &inputX2, &inputY2);
    for(int i=m-inputY2; i<m-inputY; i++)
      for(int j=inputX; j<inputX2; j++){
        board[i][j]=1;
      }
  } // input end

  int cnt=0;
  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]==0 && visited[i][j]==0){
        dfs(i, j, ++cnt);
      }
    }
  }

  printf("%d\n", cnt); // 1st output
  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      ans[visited[i][j]] += 1;
    }
  }

  sort(ans+1, ans+cnt+1);
  for(int i=1; i<=cnt; i++){
    printf("%d ",ans[i]); //2nd output
  }
}