2468 : 안전 영역 (C++)

2468번: 안전 영역

---

장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

비의 양이 정수만큼 내리는게 아니므로 아무 지역도 물에 잠기지 않을 수 있다.

값을 다 받으면서 제일 높은 위치 값을 확인 한 후

제일 높은 위치의 값 만큼만 확인해 보면된다.

각각 높이별로 DFS를 실행하여 안전한 영역의 수의 최대 개수를 비교하면서 구한 후

출력하면 끝.

오늘 문제 많이풀었다.

#include<iostream>

using namespace std;

#define MAX 100

int map[MAX][MAX];
bool visit[MAX][MAX];

int N;
int max_value = 0;
int max_height = 0;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int x, int y) {
    visit[x][y] = true;

    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
            if(visit[nx][ny] == false) {
                dfs(nx, ny);
            }
        }
    }
}

int main() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
            max_height = max_height < map[i][j] ? map[i][j] : max_height;
        }
    }

    for(int i = 1; i <= max_height; i++) {
        fill(visit[0], visit[N], false);

        for(int j = 0; j < N; j++) {
            for(int k = 0; k < N; k++) {
                if(map[j][k] <= i) {
                    visit[j][k] = true;
                }
            }
        }

        int cnt = 0;

        for(int j = 0; j < N; j++) {
            for(int k = 0; k < N; k++) {
                if(visit[j][k] == false) {
                    dfs(j, k);
                    cnt++;
                }
            }
        }
        max_value = max_value < cnt ? cnt : max_value;

    }

    if(max_value == 0) {
        max_value = 1;
    }

    cout << max_value << endl;

    return 0;
}