1. 풀이 1

#include <bits/stdc++.h>

using namespace std;

int visited[101][101];
int a[101][101];
vector<int> cnt;
int ret, tmp, n, m, k, ld_y,ld_x, ru_y, ru_x;
const int dy[4]={-1,0,1,0};
const int dx[4]={0,1,0,-1};

void dfs(int y, int x) {
    visited[y][x]=1;
    tmp++;
    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]==0) continue;
        if(visited[ny][nx]) continue;
        dfs(ny,nx);
    }
    return;
}
int main() {
    fill(&a[0][0], &a[0][0]+101*101, 1);
    cin >> m >> n >> k;
    for(int i=0;i<k;i++) {
        //(1,1) -> (2,5)  [1][1]~~[2-1][5-1]
        cin >> ld_x >> ld_y >> ru_x >> ru_y;
        for(int k=ld_y; k < ru_y; k++) {
            for(int j=ld_x; j < ru_x;j++) {
                a[k][j] = 0;
            }
        }
    } //입력받은 사각형부분 0으로 설정하기 끝
    for(int i=0;i<m;i++) { //O(m*n)
        for(int j=0;j<n;j++) {
            if(visited[i][j]==0 && a[i][j]==1) { //방문x, 그리고 방문 가능하면
                tmp=0; //tmp초기화
                dfs(i,j);
                cnt.push_back(tmp);
                ret++;
            }
        }
    }
    cout << ret << '\n';
    sort(cnt.begin(), cnt.end());
    for(int a : cnt) cout << a << ' ';
    
    return 0;
}

DFS를 이용하고, 전역변수 tmp를 이용하여 연결된 컴포넌트의 넓이를 구하는 코드이다.

2. 풀이 2

#include <bits/stdc++.h>

using namespace std;

int visited[101][101];
int a[101][101];
vector<int> cnt;
int ret, n, m, k, ld_y,ld_x, ru_y, ru_x;
const int dy[4]={-1,0,1,0};
const int dx[4]={0,1,0,-1};

int dfs(int y, int x) {
    visited[y][x]=1;
    int tmp=1;
    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]==0) continue;
        if(visited[ny][nx]) continue;
        tmp+=dfs(ny,nx);
    }
    return tmp;
}
int main() {
    fill(&a[0][0], &a[0][0]+101*101, 1);
    cin >> m >> n >> k;
    for(int i=0;i<k;i++) {
        //(1,1) -> (2,5)  [1][1]~~[2-1][5-1]
        cin >> ld_x >> ld_y >> ru_x >> ru_y;
        for(int k=ld_y; k < ru_y; k++) {
            for(int j=ld_x; j < ru_x;j++) {
                a[k][j] = 0;
            }
        }
    } //입력받은 사각형부분 0으로 설정하기 끝
    for(int i=0;i<m;i++) { //O(m*n)
        for(int j=0;j<n;j++) {
            if(visited[i][j]==0 && a[i][j]==1) { //방문x, 그리고 방문 가능하면
                cnt.push_back(dfs(i,j));
                ret++;
            }
        }
    }
    cout << ret << '\n';
    sort(cnt.begin(), cnt.end());
    for(int a : cnt) cout << a << ' ';
    
    return 0;
}

DFS를 이용하고, 전역변수 tmp없이 재귀를 이용하여 연결된 컴포넌트의 넓이를 구하는 코드이다.

3. 느낀 점

(1) 재귀를 이용한 컴포넌트 넓이 구하기

재귀를 이용해서 매번 호출마다 함수의 지역 변수에 1씩 더해주는 것이 인상적이었다.
위의 재귀를 이용한 컴포넌트 넓이 구하기 패턴을 잘 외워둬야겠다.