2583 영역 구하기

문제 링크

• 나의 풀이

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int m[101][101];
int R, C, K;
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };

int dfs(int r, int c)
{
    int ret = 1;
    m[r][c] = 1;
    for (int d = 0; d < 4; d++)
    {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nr == R || nc < 0 || nc == C || m[nr][nc])
            continue;
        if (!m[nr][nc])
        {
            m[nr][nc] = 1;
            ret += dfs(nr, nc);
        }
    }
    return ret;
}

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

    int c1, r1, c2, r2;
    vector<int> ret;
    cin >> R >> C >> K;
    while (K--)
    {
        cin >> c1 >> r1 >> c2 >> r2;
        for (int r = r1; r < r2; r++)
            for (int c = c1; c < c2; c++)
                m[r][c] = 1;
    }

    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (!m[r][c])
                ret.push_back(dfs(r, c));

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

    cout << ret.size() << "\n";
    for (int i : ret)
        cout << i << " ";
}

• 다른사람 풀이

#include <cstdio>
#include <algorithm>

int m, n;
char v[100][101];
int px[] = { -1, 1, 0, 0 };
int py[] = { 0, 0, 1, -1 };

int bfs(int x, int y)
{
    int q[10000]{};
    int b = 0, e = 0;
    int res = 0;

    q[e++] = x * 1000 + y;
    v[x][y] = 1;
    res++;

    while (b < e)
    {
        int r = q[b] / 1000;
        int c = q[b] % 1000;
        b++;

        for (int i = 0; i < 4; ++i)
        {
            int tx = r + px[i];
            int ty = c + py[i];

            if (tx >= 0 && tx < m && ty >= 0 && ty < n)
            {
                if (v[tx][ty] == 0)
                {
                    q[e++] = tx * 1000 + ty;
                    v[tx][ty] = 1;
                    res++;
                }
            }
        }
    }

    return res;
}
int main()
{
    int k;
    scanf("%d %d %d", &m, &n, &k);

    int ax, ay, bx, by;
    while (k--)
    {
        scanf("%d %d %d %d", &ax, &ay, &bx, &by);

        for (int i = ax; i < bx; ++i)
        {
            for (int j = ay; j < by; ++j)
            {
                v[j][i] = 1;
            }
        }
    }

    int p = 0, cnt = 0;
    int arr[5000]{};
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (v[i][j] == 0)
            {
                cnt++;
                arr[p++] = bfs(i, j);
            }
        }
    }

    printf("%d\n", cnt);

    std::sort(arr, arr + p);
    for (int i = 0; i < p; ++i) printf("%d ", arr[i]);

    return 0;
}