2468 안전영역

#include <stdio.h>
#include <string.h>
 
int arr[105][105] = { 0 };
int chk[105][105] = { 0 };
 
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
 
void dfs(int y, int x, int w) {
    chk[y][x] = -1;
 
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx <= 0 || xx > w || yy <= 0 || y > w)
            continue;
        if (chk[yy][xx] != 0)
            continue;
        dfs(yy, xx, w);
    }
}
 
int rainning(int rain, int w) {
    memset(chk, 0, sizeof(chk));
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= w; j++) {
            if (arr[i][j] <= rain) {
                chk[i][j] = 1;
            }
        }
    }
 
    int rst = 0;
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= w; j++) {
            if (chk[i][j] == 0) {
                rst++;
                dfs(i, j, w);
            }
        }
    }
 
    return rst;
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    int mini = 101, maxi = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
 
            if (mini > arr[i][j])
                mini = arr[i][j];
            if (maxi < arr[i][j])
                maxi = arr[i][j];
        }
    }
 
    int region = 0;
    for (int i = mini-1; i <= maxi; i++) {
        int tmp = rainning(i, n);
        if (tmp > region)
            region = tmp;
    }
    printf("%d", region);
}

BFS 를 쓰려하다가 DFS 를 썼다.

BFS의 경우, 특정한 지점에서 시작하기에 유리하다.

근데 이 문제의 경우, 특정한 지점에서 시작했다고 보기가 힘들어서 DFS를 이용해서 처리했다.

그나마 쉬운 DFS 유형이여서 쉽게 해결이 가능했다.