[C++] BAEKJOON 2583 영역 구하기

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

2583번: 영역 구하기

dfs 를 이용해서 구현하였습니다.

board 배열에서 가지 못하는 부분과 이미 간 부분을 1로 체크함으로서 visited 배열을 한 번에 표현할 수 있습니다. 전체 board 를 순회하며 갈 수 있는 부분을 만나면 그 부분부터 dfs 를 통해 몇 칸이 있는지 확인해주고 더 이상 갈 곳이 없으면 v 벡터에 추가해줍니다. 따라서 v 벡터는 분리된 영역의 수가 되고, 각 값은 몇 칸으로 나누어져 있는지를 확인 할 수 있습니다.

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

using namespace std;

int board[100][100];

int dx[] ={0,0,1,-1};
int dy[] ={1,-1,0,0};

int cnt = 0;

void dfs(int y,int x, int M, int N){
    
    board[y][x] = 1;
    cnt++;
    
    for (int a=0;a<4;a++){
        int nx = x + dx[a];
        int ny = y + dy[a];
        if (0<=nx && nx<N && 0<=ny && ny<M)
            if (board[ny][nx]==0)
                dfs(ny,nx,M,N);
    }
}

int main(int argc, const char * argv[]) {
    
    int M,N,K;
    
    cin >> M >> N >> K;
    
    for (int i=0;i<K;i++){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        for (int x=x1;x<x2;x++){
            for (int y=y1;y<y2;y++){
                board[y][x] = 1;
            }
        }
    }
    
    vector <int> v;

    for (int i=0;i<M;i++){
        for (int j=0;j<N;j++){
            if (!board[i][j]){
                cnt = 0;
                dfs(i,j,M,N);
                v.push_back(cnt);
            }
        }
    }
    
    sort(v.begin(), v.end());
    cout << v.size() << "\n";
    for (int i=0;i<v.size();i++){
        cout << v[i] << " ";
    }
    

    return 0;
}