[백준]영역구하기

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

섬인덱싱 + 섬의 넓이(개수 체크)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int M, N, K;
int map[100][100], isV[100][100];
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
vector<int> v;
int ans = 0, width = 0;
 
void dfs(int r, int c) {
    isV[r][c] = 1;
    width++; //넓이 체크
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr < 0 || nc < 0 | nr >= M || nc >= N || isV[nr][nc] == 1 || map[nr][nc] == 1) continue;
        dfs(nr, nc);
    }
}
 
void solve() {
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 0 && isV[i][j] == 0) {
                ans++; //섬의 개수
                width = 0; //섬의 넓이
                dfs(i, j);
                v.push_back(width);
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", ans);
    for (int i = 0; i < v.size(); i++) printf("%d ", v[i]);
}
 
int main() {
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++) {
        int r1, c1, r2, c2;
        cin >> c1 >> r1 >> c2 >> r2;
        for (int r = r1; r < r2; r++) for (int c = c1; c < c2; c++) map[r][c] = 1;
    }
    solve();
    return 0;
}