영역 구하기 2583

문제

접근 방법

탐색 문제이다. BFS, DFS를 사용하면 풀 수 있다.
영역을 구분해주며 직사각형 영역이 아닌 경우에만 넓이를 정답 벡터에 저장해둔다.
어차피 넓이는 눈금 1개당 1이므로 탐색한 만큼 넓이가 된다.

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
bool box[101][101], visited[101][101];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, M, N, K;
int bfs(int x, int y, bool isBox)
{
    if (visited[x][y])
    {
        return 0;
    }
    visited[x][y] = true;
    int cnt = 1;
    for (int i = 0; i < 4; ++i)
    {
        int nextX = dx[i] + x, nextY = dy[i] + y;
        if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && box[nextX][nextY] == isBox)
            cnt += bfs(nextX, nextY, isBox);
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(box, false, sizeof(box));
    memset(visited, false, sizeof(visited));
    int cnt = 0;
    vector<int> answer;
    cin >> M >> N >> K;
    while (K--)
    {
        int lx, ly, rx, ry;
        cin >> lx >> ly >> rx >> ry;
        for (int i = lx; i < rx; ++i)
        {
            for (int j = ly; j < ry; ++j)
            {
                box[i][j] = true;
            }
        }
    }
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (visited[i][j])
                continue;
            bool isBox = box[i][j];
            int cnt = bfs(i, j, isBox);
            if (!isBox)
            {
                answer.push_back(cnt);
            }
        }
    }
    sort(answer.begin(), answer.end());
    cout << answer.size() << "\n";
    for (int a : answer)
    {
        cout << a << " ";
    }
    return 0;
}

풀이

bfs로 풀었다.
직사각형 영역인지, 이미 방문한 영역인지에 대한 이차원 bool 배열을 선언하고 직사각형 영역만큼 표시해준다.
그리고 bfs를 돌고 범위 안에서 같은 영역일 경우에만 탐색하게 해준다.
만약 직사각형 영역이 아니면 bfs를 돌고 나왔을 때 넓이를 정답에 저장해준다. 마지막에 정렬해주고 출력해주면 된다.

생각보다 자주 친숙해 보이는 문제 같기도 하다.