[KOI] 백준 2583 - 영역 구하기

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

힌트

좌표로 인해 블록 색칠에 어려움을 겪고 있다면 예제에서 제시된 좌표에서 같은 행, 같은 열끼리 이은 선분의 길이를 살펴보자. 무언가 알 수 있을지도 모른다.

풀이

이 문제는 윈도우 좌표계가 아닌 직교 좌표계에서 격자의 중앙이 아닌 모서리의 좌표가 주어진다.

 

일단 우리가 쉽게 접하는 윈도우 좌표계로 먼저 좌표를 바꿔주자.

 

(M - Y좌표) 를 계산해주면 우리가 원하는 행을 구할 수 있다. 그리고 윈도우 좌표계에서는 X와 Y랑 반대가 되니 이 둘을 스왑해서 R, C 좌표로 만들어주자.

 

저렇게 좌표를 바꾸고 난 뒤 사각형을 채우기 용이하도록 좌측 하단 -> 우측 상단으로 주어진 좌표를 좌측 상단 -> 우측 하단으로 바꿔주도록 하자.

 

그리고 격자의 모서리 좌표가 주어지는 것에 애를 먹을 수 있지만 같은 행, 같은 열끼리 이은 선분의 거리를 보면 우리가 원하는 블록 길이보다 1 더 큰 것을 발견할 수 있다.

 

이것에 착안하여 시작점의 X와 Y 좌표에 1씩 더해 사각형을 칠하면 제시된 그림과 같은 사각형 영역을 얻을 수 있다. 다만 이렇게 하면 첫 행과 첫 열이 빈 영역이 되는데 이는 사전에 칠해주는 전처리를 하면 된다.

 

위에 말한 빈 영역을 유의하며 사각형 영역들을 칠해주자.

 

참고로 imos법을 이용하면 주어진 여러 영역을 효율적으로 칠할 수 있음이 알려져 있다. 정말 좋은 기술이니 참고할 것을 강력 권장한다.

 

영역을 다 칠했으면 빈 영역을 발견할 때마다 BFS를 수행해서 영역의 개수, 각 영역의 크기를 구해주면 된다.

 

영역의 크기는 오름차순으로 출력하는 조건에 유의하여 얻은 영역의 크기들을 정렬하도록 한다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;
using ll = long long;
using pii = pair<int, int>;

int n, m, q;

int imos[104][104];
bool visited[104][104];
int cnt;

void solve()
{
  cin >> n >> m >> q;
  imos[n + 1][0] = 1;
  imos[0][m + 1] = 1;

  for (int i = 0; i < q; ++i)
  {
    int h, w, r, c;
    cin >> h >> w >> r >> c;

    int tmp = h;
    h = (n - w);
    w = tmp;
    tmp = r;
    r = (n - c);
    c = tmp;
    swap(h, r);
    ++h, ++w;

    ++imos[h][w];
    ++imos[r + 1][c + 1];
    --imos[r + 1][w];
    --imos[h][c + 1];
  }

  for (int i = 0; i < 104; ++i)
  {
    for (int j = 1; j < 104; ++j)
    {
      imos[i][j] += imos[i][j - 1];
    }
  }

  for (int i = 0; i < 104; ++i)
  {
    for (int j = 1; j < 104; ++j)
    {
      imos[j][i] += imos[j - 1][i];
    }
  }

  for (int i = 0; i <= m; ++i)
    imos[0][i] = 1;
  for (int i = 0; i <= n; ++i)
    imos[i][0] = 1;

  priority_queue<int, vector<int>, greater<int>> ans;

  for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; j <= m; ++j)
    {
      if (imos[i][j] || visited[i][j]) continue;

      ++cnt;
      queue<pii> q;
      q.push({i, j});
      int tmp = 0;
      visited[i][j] = 1;

      while (q.size())
      {
        auto cur = q.front();
        q.pop();
        ++tmp;
        for (int k = 0; k < 4; ++k)
        {
          int nr = cur.first + ("2213"[k] - '2');
          int nc = cur.second + ("1322"[k] - '2');
          if (nr < 1 || nc < 1 || nr > n || nc > m || imos[nr][nc] || visited[nr][nc])
            continue;
          q.push({nr, nc});
          visited[nr][nc] = true;
        }
      }

      ans.push(tmp);
    }
  }

  cout << cnt << '\n';
  while (ans.size())
  {
    cout << ans.top() << ' ';
    ans.pop();
  }
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}

제출 기록