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

문제 링크

2583번: 영역 구하기

풀이

영역의 개수와 넓이를 구하는 BFS문제

1. 먼저 원점이 왼쪽 밑이고, 입력받는 x와 y의 값이 칸 기준이 아니기 때문에 바꿔줘야할 필요가 있다.
   1. x1과 x2는 왼쪽에서부터이므로 사각형의 x범위는 x1~x2-1이 된다.
   2. y1과 y2는 밑에서부터이므로 사각형의 y범위는 m-1-(y2-1)~m-1-y1이 된다.
2. 그렇게 입력 받은 범위를 1로 채우고 처음부터 모눈종이를 돌면서 0인 부분부터 탐색을 시작한다.
   1. 영역의 개수를 구해줘야하므로 cnt++ 해준다.
   2. BFS 함수로 탐색을 하는데, queue를 이용한다. visit 배열 없이 바로 board에 체크해준다.
   3. 영역 넓이를 구해야하므로 지역 변수 cnt를 0으로 초기화 한뒤, queue가 비어서 더이상 나아갈 수 없을 때까지 진행한다.
   4. 배열의 범위를 넘어가거나, 1일 경우에는 continue 해주고, 아니라면 1로 바꾸어 더이상 탐색을 안하도록 한 뒤, q에 추가한다.
3. 그렇게 BFS가 실행될 때마다 answer에 추가해주고, board가 모두 1이 되면 탐색은 끝이다.
4. cnt를 출력한 뒤, answer를 정렬해서 출력해주면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int dy[4] = { 0,1,0,-1 };
int dx[4] = { -1,0,1,0 };

int BFS(vector<vector<int>> &board, int y, int x)
{
    queue<pair<int, int>> q;
    q.push({ y,x });
    board[y][x] = 1;

    int cnt = 0;
    while (!q.empty())
    {
        cnt++;
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size()) continue;
            if (board[ny][nx] == 1) continue;
            board[ny][nx] = 1;
            q.push({ ny, nx });
        }
    }

    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int m, n, k;
    cin >> m >> n >> k;

    vector<vector<int>> board(m, vector<int>(n, 0));
    for (int i = 0; i < k; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int y = m - 1 - (y2 - 1); y <= m - 1 - y1; y++)
        {
            for (int x = x1; x <= x2 - 1; x++)
            {
                board[y][x] = 1;
            }
        }
    }

    vector<int> answer;
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (board[i][j] == 0)
            {
                cnt++;
                answer.push_back(BFS(board, i, j));
            }
        }
    }

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

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