[백준] 영역구하기 DFS

2583번 영역구하기

    //
    // Created by JayPark on 2020/05/09.
    //

    #include "algo.h"
    using namespace std;
    // dfs 사용 선언
    void dfs(int x, int y);
    // 왼쪽으로 90도 기울어졌다고 생각하면 원래 배열의 모양이 나온다.
    // 기본 입력 변수
    int M, N, K;
    // 맵 선언
    int map[101][101];
    // 방문체크를 위한 배열
    bool visited[101][101];
    // 방(영역)의 개수를 세기위한 카운트 변수
    int cnt;
    // 4방탐색을 위한 값 2개
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    int main(){
        cin >> M >> N >> K;
        // map 구현하기 (사각형 그리기)
        for(int t=0;t<K;t++){
            int x1, x2, y1, y2;
            // 사각형을 그릴 좌표값
            cin >> x1 >> y1 >> x2 >> y2;
            for(int i=M-y2;i<M-y1;i++){
                for(int j=x1;j<x2;j++){
                    map[i][j] = 1;
                }
            }
        }
        // 영역크기를 저장할 벡터 배열
        vector<int> gasu;
        for(int i=0;i<M;i++) {
            for (int j = 0; j < N; j++) {
                cnt = 0;
                if (!visited[i][j] && map[i][j] == 0) {
                    cnt++;
                    dfs(i, j);
                    // 영역의 크기를 저장
                    gasu.push_back(cnt);
                }
            }
        }
        // 정렬
        sort(gasu.begin(), gasu.end());
        int rs = gasu.size();
        // 출력부
        cout << rs << endl;
        for(int i=0; i < rs-1; i++){
            cout << gasu[i] << " ";
        }
        cout << gasu[rs-1] << endl;
    }
    // 노드 좌표를 인자로서 받는다.
    void dfs(int x, int y){
        // dfs (깊이 우선 탐색) 해보기
        visited[x][y] = true;
        // 상하좌우 탐색을 한다.
        for(int k=0;k<4;k++){
            // 현재값에 상하좌우 탐색 방법
            int nx = x + dx[k];
            int ny = y + dy[k];
            // 방문한 방이면 무시
            if(visited[nx][ny]) continue;
            // 영역이 아니면 무시
            if(map[nx][ny] == 1) continue;
            // 범위를 벗어나지 않는다면
            if(nx >= 0 && ny >=0 && nx < M && ny < N){
                // dfs 재귀
                dfs(nx, ny);
                // 카운트 올리기 
                ++cnt;
            }
        }
    }