백준 2583:영역 구하기

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

백준 2583번 문제입니다. 제가 요즘 공부하고 있는 dfs활용 문제에요. 밑에는 제 코드입니다.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX 101
 
int grid[MAX][MAX];
bool visited[MAX][MAX];
int M,N;
int size, cnt;
 
void dfs(int grid[MAX][MAX], int r, int c) {
    visited[r][c] = true;
    size++;
 
    if (r > 0 && grid[r][c] == grid[r - 1][c] && !visited[r - 1][c]) dfs(grid, r - 1, c);
    if (c > 0 && grid[r][c] == grid[r][c - 1] && !visited[r][c - 1]) dfs(grid, r, c - 1);
    if (r < N && grid[r][c] == grid[r + 1][c] && !visited[r + 1][c]) dfs(grid, r + 1, c);
    if (c < N && grid[r][c] == grid[r][c + 1] && !visited[r][c + 1]) dfs(grid, r, c + 1);
}
 
int main(void) {
    
    int k; int SIZE[MAX];
 
    scanf("%d%d%d", &M, &N, &k);
    for (int i = 0; i < M; i++) {
        for (int k = 0; k < N; k++) {
            grid[i][k] = 1;
        }
    }
    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        for (int r = y1; r < y2; r++) {
            for (int c = x1; c < x2; c++) {
                grid[r][c] = 0;
            }
        }
    }
 
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            if (!visited[r][c] && grid[r][c]) {
                dfs(grid,r,c);
                SIZE[cnt] = size;
                size = 0;
                cnt++;
            }
        }
    }
    for (int i = 0; i < cnt-1; i++) {
        for (int k = 0; k < cnt - i - 1; k++) {
            if (SIZE[k] > SIZE[k + 1]) {
                int t = SIZE[k];
                SIZE[k] = SIZE[k + 1];
                SIZE[k + 1] = t;
            }
        }
    }
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++) {
        printf("%d\n", SIZE[i]);
    }
 
    return 0;
}

이번문제는 체크된박스 외의 범위의 갯수와 크기를 구하는 문제였어요.

6~9:배열과 방문했는지 체크하는 배열, 가로세로MN, 크기size와 갯수cnt 선언

11~19:dfs함수입니다. 탐색을 시작하면 방문한 좌표를 방문했다고 체크하고 크기를 하나늘려줍니다. if조건문은 좌표가 정해진 범위를 넘는지, 이어져 있는지, 방문했는지 확인 합니다.

25~30:저는 반대로 주어진 범위만큼을 1로 초기화 해두었습니다.

31~39:직사각형의 양 꼭짓점이 주어지면 0으로 초기화 했습니다. 이렇게 하게되면 나머지 부분이 1로 남아있으니 그부분을 탐색하면 됩니다. 하지만 저는 왼쪽위를 0,0으로 생각했습니다. 따라서 제 코드의 모양은 이런식으로 구현됩니다!!

41~50:dfs함수로 탐색을 하는 부분입니다. 측정된 크기를 크기배열에 저장하고 0으로 초기화 후 갯수를 하나 증가시킵니다.

51~59:크기배열을 정렬하는 코드입니다.(버블정렬)

60~:갯수와 크기 출력