[백준] 2468 안전영역 c++

 

문제 링크 https://www.acmicpc.net/problem/2468

Key

• 0부터 제일 높은 지역의 높이까지 1씩 침수높이를 올려가면서 답을 찾으면 된다.
• 침수된 지역을 0으로 만들어 침수가 되지 않은 곳과 차별을 두었고, 이를 기반으로 0이 아닌 지역에 대해서 DFS탐색 하도록 하였다.
• 문제 조건에서 아무 지역도 물에 잠기지 않을 수도 있다고 했으므로 높이가 0일 때부터 탐색해야 한다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 101;
int n;
int arr[MAX][MAX];
bool visited[MAX][MAX];
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
int maxh; //지역 최대높이
int answer;
 
void rain(int height) { //침수된 곳 0으로 만들기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] <= height) {
                arr[i][j] = 0;
            }
        }
    }
}
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (visited[nx][ny])
            continue;
        if (nx < 0 || nx >= n || ny < 0 || ny >= n)
            continue;
        if (arr[nx][ny] == 0)
            continue;
        visited[nx][ny] = true;
        dfs(nx, ny);
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            maxh = max(maxh, arr[i][j]); //최대 지역높이 구하기
        }
    }
 
    for (int k = 0; k <= maxh; k++) {
        rain(k); //침수 발생
 
        int cnt = 0; //안전한 영역 수
        memset(visited, false, sizeof(visited)); //방문 배열 초기화
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] != 0 && visited[i][j] != 1) {
                    visited[i][j] = true;
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        answer = max(answer, cnt); //안전한 영역이 가장 많은 곳이 정답
    }
    cout << answer;
}