백준 2583 (C++) 영역 구하기

아이디어

1. input

2차원 배열을 예제의 모양대로 

 

처럼 표현하기 위해서 그대로 넣을 수 없고

 

        for (int i = y1; i < y2; i++) {
            for (int j = x1; j < x2; j++) {
                arr[m-i-1][j] = 1;
            }
        }

 

를 거쳐야 한다.

 

2. dfs

dfs를 진행하면서, 인접한 행렬은 visit되었다고 체크해주고,

main함수에서 이차원 배열이 visit되었는지 세면서 섬처럼 인접한 부분을 cnt해주면 분리된 영역의 개수를 알 수 있다.

 

여기서 각 분리된 영역의 넓이를 알기 위해

visit되지 않은 칸에 (값은 0) dfs함수가 재귀적으로 호출될 때마다 영역의 넓이를 더해줬다.

그리고 매 영역마다 넓이를 0으로 다시 초기화한다.

 

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int n, m, k;
int arr[101][101] = {0, };
bool visit[101][101] = {false, };
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int cnt = 0;
int area = 0;
vector<int> v;

int dfs(int x, int y) {
    visit[x][y]= true;
    area++;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
            continue;
        }
        if (!visit[nx][ny] && arr[nx][ny] == 0) {
            dfs(nx, ny);
        }
    }
    return area;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> m >> n >> k;
    for (int t = 0; t < k; t++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int i = y1; i < y2; i++) {
            for (int j = x1; j < x2; j++) {
                arr[m-i-1][j] = 1;
            }
        }
    }
    /*
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i][j] << " ";
        }
        cout << '\n';
    }
     */
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visit[i][j] && arr[i][j] == 0) {
                cnt++;
                int a = dfs(i, j);
                v.push_back(a);
                area = 0;
            }
        }
    }
    sort(v.begin(), v.end());
    cout << cnt << '\n';
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}