백준 2583번 영역 구하기( C++ )

문제

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

2583번: 영역 구하기

 

해설

집단의 수 및 크기를 구하는 문제 => dfs / bfs

집단의 수는 정해지지 않은 수이기 때문에 동적할당 필요 => vector사용

 

코드

#include <bits/stdc++.h>
using namespace std;
int m, n, k, ret1, ret2, tmp, x1, x2, y11, y2;
int visited[104][104];
int mp[104][104];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
vector<int> v;
 
int dfs(int y, int x)
{
  visited[y][x] = 1;
  int cnt = 1;
  for (int i = 0; i < 4; i++)
  {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[ny][nx] == 1 || mp[ny][nx] == 1)
      continue;
    cnt += dfs(ny, nx);
  }
  return cnt;
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> m >> n >> k;
  for (int i = 0; i < k; i++)
  {
    cin >> x1 >> y11 >> x2 >> y2;
    for (int x = x1; x < x2; x++)
    {
      for (int y = y11; y < y2; y++)
      {
        mp[y][x] = 1;
      }
    }
  }
 
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (mp[i][j] == 0 && visited[i][j] == 0)
      {
        v.push_back(dfs(i, j));
        ret1++;
      }
    }
  }
 
  sort(v.begin(), v.end());
  cout << ret1 << "\n";
  for (int s : v)
    cout << s << " ";
}