[백준 / BOJ] C++ 2583 영역 구하기

2583번: 영역 구하기

 

문제

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

2583번: 영역 구하기

 

 

풀이

모눈종이 위의 몇 가지 직사각형을 제외한 공간의 수와 각각의 넓이를 오름차순으로 출력하는 문제다. 먼저 2차원 배열을 만들고 직사각형을 채워야 하는데 입력은 모눈종이의 좌표로 입력되는 반면 배열의 인덱스와 맞추기 위해서 2중 for문을 사용해 (x1, y1)부터 (x2, y2)까지 -1로 색칠을 해준다.

 

배열이 -1이 아닌 공간에 대해 bfs를 시행한다. cnt 변수를 만들어 몇 번째 빈 공간인지 수를 세며 bfs에서는 값이 -1이 아닌 인접 공간에 대해 cnt 번호를 부여한다. 모든 공간을 탐색한 다음 모눈종이의 각 칸에 매겨진 번호의 수를 센다. 이 수를 정렬한 다음 출력 형식에 맞추어 cnt와 정렬한 수를 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

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

void bfs(int xx, int yy) {
  queue<pair<int, int>> q;
  q.push({xx, yy});
  // cnt번째 공간임을 표시
  visited[xx][yy] = ++cnt;
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    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)
        continue;
      if (!visited[nx][ny]) {
        q.push({nx, ny});
        // cnt번째 공간임을 표시
        visited[nx][ny] = cnt;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> m >> n >> k;
  while (k--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    // 직사각형 색칠
    for (int i = x1; i < x2; i++)
      for (int j = y1; j < y2; j++)
        visited[i][j] = -1;
  }
  // 각각의 빈 공간에 대해 bfs
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (!visited[i][j])
        bfs(i, j);
  // 넓이를 저장하는 배열
  vector<int> ans(cnt + 1, 0);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (visited[i][j] != -1)
        ans[visited[i][j]]++; // N번째 공간의 넓이 1 증가
  sort(ans.begin(), ans.end()); // 정렬
  cout << cnt << '\n';
  for (int i = 1; i <= cnt; i++)
    cout << ans[i] << ' ';
  return 0;
}