본인 풀이

#include<bits/stdc++.h>
using namespace std;

int visited[101][101];
int a[101][101];
int m, n, k, area = 0;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    visited[y][x] = 1;
    area++;

    for (int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || nx < 0 || ny >= m || nx >= n){
            continue;
        }

        // 방문하지 않은 곳이면서 수압보다 높은 위치의 타일
        if(!a[ny][nx] && visited[ny][nx] == 0){
            dfs(ny, nx);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> m >> n >> k;
    vector<int> ret;

    // 영역 내에 직사각형 제작
    for (int i = 0; i < k; i++){
        int sx, sy, destx,desty;

        cin >> sx >> sy >> destx >> desty;

        for (int j = sy; j < desty; j++){
            for (int l = sx; l < destx; l++){
                a[j][l] = 1;
            }
        }
    }

    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] || visited[i][j])
            {
                continue;
            }
            dfs(i, j);
            ret.push_back(area);
            area = 0;
        }
    }

    sort(ret.begin(), ret.end());
    cout << ret.size() << "\n";
    for (int i : ret)
    {
        cout << i << " ";
    }
    cout << "\n";

    return 0;
}

1. DFS로 풀었음
2. 직사각형이라서 M과 N범위 설정 관련해서 헷갈렸는데, 굳이 상관하지 않고 그냥 그대로 풀이하면 됨
3. 이차원배열 y값의 증분은 우리가 수학에서 익히는 x-y좌표계에서 y축이 반대로 이루어짐. 그냥 뒤집어서 풀이해도 별 상관 없음
4. 방문 가능한 영역을 a[i][j] = 1로 표현하는데, 이때 1을 넣을지 0을 넣을지 의미론적으로 잘 선택해야함

모범 답안

dfs구현시 나는 함수를 void형으로 선언하고 전역변수를 통해 연결 컴포넌트 넓이를 계산했는데, 재귀적으로 호출하며 dfs를 int값을 리턴하도록 구현하는 것도 가능하다.

int dfs(int y, int x){
    visited[y][x] = 1;
    int ret = 1;

    for(int i=0; i<4; i++){
        // ..

        // 나머지 돌아다닐 좌표들을 순회한다
        // 최종 순회 후에 ret에 연결 컴포넌트 넓이가 담기게 됨
        ret += dfs(ny, nx);
    }
    return ret;
}