백준 2468 / 안전 영역

가장 높은 곳을 알아낸다음

0부터 가장 높은 곳까지 모든 경우에서

비가 찬 곳 1 / 안 찬 곳 0 으로 해서

DFS던 BFS던 인접 영역이 몇갠지 구하면 된다.

DFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>
#include <algorithm>
 
using namespace std;
 
int n;
int map[101][101];
int map2[101][101];
bool check[101][101];
int high=0;
 
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
 
void go(int x, int y) {
 
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
            if (map2[nx][ny] == 0 && check[nx][ny] == false) {
                check[nx][ny] = true;
                go(nx, ny);
            }
        }
    }
 
    return;
 
 
 
}
int main() {
    
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
 
 
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            high = max(high, map[i][j]);
        }
    }
 
    vector<int>ans;
 
    for (int i = 0; i <= high; i++) {
        
        int area=0;
 
 
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (map[j][k] <= i) {
                    map2[j][k] = 1;
                }
                else
                    map2[j][k] = 0;
            }
        }
 
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (map2[j][k] == 0 && check[j][k]==false) {
                    check[j][k] = true;
                    area++;
                    go(j, k);
                }
            }
        }
 
        
        ans.push_back(area);
        memset(check, false, sizeof(check));
 
    }
    
 
    sort(ans.begin(), ans.end());
    cout << ans[ans.size()-1];
 
 
}