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

문제 링크 : www.acmicpc.net/problem/2583

2583번: 영역 구하기

>풀이

 

처음에는 영역 탐색? bfs로 풀면 바로 풀리겠네? 하고 풀다가 생각해보니 넓이를 구하는거는 dfs로 탐색하는게 구현이 편할 것 같더라고요. 그래서 dfs로 풀었습니다.

 

결과 값을 저장하고, 정렬해야하니, vector와 sort를 사용합시다 :)

 

아무 생각없이 visited배열을 visit로 이름짓고 풀다가 컴파일 에러났네요 ㅋㅋㅋ

#include <bits/stdc++.h>
using namespace std;

int moveX[4] = {1, -1, 0, 0};
int moveY[4] = {0, 0, 1, -1};

int M, N, K;
int cnt;
int arr[101][101];
bool visited[101][101];
vector<int> res;

void dfs(int x, int y) {
        int nx, ny;

        visited[x][y] = true;
        cnt++;

        for (int i = 0; i < 4; i++) {
                nx = x + moveX[i];
                ny = y + moveY[i];

                if (nx >= 0 && ny >= 0 && nx < M && ny < N && !visited[nx][ny]) {
                        dfs(nx, ny);
                }
        }
}

int main(void) {
        scanf("%d %d %d", &M, &N, &K);
        for (int i = 0; i < K; i++) {
                int x1, x2, y1, y2;
                scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                for (int j = y1; j < y2; j++) {
                        for (int k = x1; k < x2; k++) {
                                arr[j][k] = 1;
                                visited[j][k] = true;
                        }
                }
        }
        for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                        if (arr[i][j] == 0 && visited[i][j] == false) {
                                cnt = 0;
                                dfs(i, j);
                                res.push_back(cnt);
                        }
                }
        }
        sort(res.begin(), res.end());
        
        int size = res.size();

        printf("%d\n", size);
        for (int i = 0; i < size; i++)
                printf("%d ", res[i]);

        return 0;
}

(개발 환경 : vs code)