2468 안전영역

BOJ::2468 안전영역

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

1. 높이로 주어지는 값이 1~100이므로 1~100까지 잠길 수 있는 모든 경우에 대해 탐색

2. 탐색하면서 안전영역의 최대값을 저장

#include <iostream>
 
int map[100][100];
int tmp[100][100];
bool visited[100][100];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int n;
 
void dfs(int x,int y) {
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if (ax >= 0 && ay >= 0 && ax < n&&ay < n 
            && !visited[ax][ay] && tmp[ax][ay] != 0) {
            dfs(ax, ay);
        }
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    int cnt = 0;
    int M = 0;
    for (int k = 1; k <= 100; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i][j] = map[i][j] - k;
                if (tmp[i][j] < 0) tmp[i][j] = 0;
                visited[i][j] = 0;
            }
        }
 
        cnt = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (tmp[i][j] != 0 && !visited[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        if (cnt > M) M = cnt;
    }
    if (M == 0)M = 1;
    printf("%d\n", M);
}