2583 영역 구하기

2583. 영역 구하기 / c++ / Silver1 / 42분

문제

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

1. M x N 인 모눈종이에
2. K개의 직사각형을 그린다.
3. 직사각형이 아닌 부분의 영역의 갯수와 그 크기를 오름차순으로 출력하라.

접근 방식

그래프, BFS

1. 직사각형의 위치를 받고 fill로 해당 칸을 1로 채워준다.
2. BFS로 0인 칸을 돌아다니며 크기를 세주고, 1로 바꿔준다.
3. BFS값을 vector에 넣어준다.
4. vector.size() 출력, vector를 sort해서 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int Y, X, K;
int board[100][100] = {};
int yPos1, xPos1, yPos2, xPos2;
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { -1, 1, 0, 0 };
vector<int> v;

int BFS(int y, int x)
{
    queue<pair<int, int>> q;
    q.push({ y, x });

    int answer = 0;

    while (!q.empty())
    {
        pair<int, int> now = q.front(); q.pop();
        if (board[now.first][now.second] == 1) continue;
        board[now.first][now.second] = 1;
        answer++;

        for (int i = 0; i < 4; ++i)
        {
            int nextY = now.first + dy[i];
            int nextX = now.second + dx[i];

            if (nextY < 0 || nextY == Y || nextX < 0 || nextX == X) continue;
            if (board[nextY][nextX] == 1) continue;
            q.push({ nextY, nextX });
        }
    }

    return answer;
}


int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> Y >> X >> K;

    for (int i = 0; i < K; ++i)
    {
        cin >> xPos1 >> yPos1 >> xPos2 >> yPos2;
        for (int j = yPos1; j < yPos2; ++j)
        {
            fill(board[j] + xPos1, board[j] + xPos2, 1);
        }
    }

    for (int i = 0; i < Y; ++i)
    {
        for (int j = 0; j < X; ++j)
        {
            if (board[i][j] == 0)
            {
                v.push_back(BFS(i, j));
            }

        }
    }

    sort(v.begin(), v.end());

    cout << v.size() << '\n';

    for (int i = 0; i < v.size(); ++i)
    {
        cout << v[i] << ' ';
    }
    cout << '\n';

    return 0;
}

다시 생각해 볼 점

1. M, N이 100일때, DFS로는 최대 9999번 재귀함수 호출을 해야한다. (stack overflow 발생)
2. 모눈 종이여서 좌표를 제공하는 것을 해당 칸의 번호로 오인하여 실수하였다. 문제를 잘 읽어볼것