백준 2468 안전 영역

1. 비가 아예 안오는 경우도 고려해야 합니다.

/*
0950 안전 영역
*/
 
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
#define SIZE 101 // 101
 
int map[SIZE][SIZE];
int map_store[SIZE][SIZE];
int visit[SIZE][SIZE];
struct point {
    int x, y;
};
queue<point> que;
int maxVal;
int N;
int highest;
int lowest = 102;
int x, y, nx, ny;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int safeArea = 0;
 
void problemIn() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            map_store[i][j] = map[i][j];
            highest = max(highest, map[i][j]);
            lowest = min(lowest, map[i][j]);
        }
    }
}
 
void copy_map(int(*a)[SIZE], int(*b)[SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            b[i][j] = a[i][j];
        }
    }
}
 
void visit_init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visit[i][j] = 0;
        }
    }
}
 
void map_change(int height) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] <= height) map[i][j] = 0; // 물에 잠기면 0
            else { map[i][j] = 1; } // 안전영역 1;
        }
    }
}
 
void bfs() {
 
    while(!que.empty()) {
        x = que.front().x;
        y = que.front().y;
        que.pop();
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if (map[nx][ny] == 1 && visit[nx][ny] == 0) {
                    visit[nx][ny] = 1;
                    que.push({ nx,ny });
                }
            }
        }
    }
}
/*
비가 하나도 오지 않는 경우?
*/
 
void solve() {    
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
 
        }
    }
 
 
    for (int i = lowest; i < highest; i++) {
        map_change(i);
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if(map[j][k] == 1 && visit[j][k] == 0){
                    visit[j][k] = 1;
                    que.push({ j,k });
                    safeArea++;
                    bfs();
                }
            }
        }
 
        maxVal = max(safeArea, maxVal);
        safeArea = 0;
        copy_map(map_store, map);
        visit_init();
    }
}
 
int main() {
    problemIn();
    solve();
    if (maxVal == 0) maxVal = 1; // 비가 안오는 경우
    cout << maxVal << endl;
    return 0;
}