[백준 2468번] 안전 영역 C++

www.acmicpc.net/problem/2468

2468번: 안전 영역

 

정석적인 DFS 문제였습니다.

완전탐색을 위해 시간복잡도를 고렸는데 그래봤자 최대 N 이 100이기때문에 완전탐색이 가능했습니다.

제가 전역변수에 dx, dy라고 적은 위,아래,왼쪽,오른쪽 이동법은 많이 쓰이는 방법이니 패스하구..

 

비가 내린 수위를 처음부터 끝까지 완전탐색 하며 매 수위마다 나온 안전지대의 갯수를

매번 최대값 도출 함수 max를 이용해서 갱신해줬습니다.

 

최후의 수위인 99까지 돌았을때 나온 result 값이 최대 많은 안전지대의 수 입니다.

 

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
int n;
int arr[101][101];
bool visit[101][101];
//위,아래,좌,우 탐색을 위한 좌표 변경값
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
 
int cnt;
//진짜 정석적인 위아래 좌표 이동에 쓰이는 dfs
void dfs(int rain, int a, int b) {
    visit[a][b] = true;
    for (int i = 0; i < 4; i++) {
        int x = a + dx[i];
        int y = b + dy[i];
        if (x >= 0 && y >= 0 && x < n && y < n) {
            if (arr[x][y] > rain && !visit[x][y])
                dfs(rain, x, y);
        }
    }    
}
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
 
    int result = 0;
    //장마는 0~99의 높이까지 내린다고 가정하고 완전탐색
    for (int k = 0; k < 100; k++) {
        //매 경우에 visit와 안전영역의 갯수 카운트 초기화
        memset(visit, false, sizeof(visit));
        cnt = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                //지역이 수위보다 높은곳, 그리고 아직 방문하지 않았으면 dfs
                if (arr[i][j] > k && !visit[i][j]) {
                    dfs(k, i, j);
                    cnt++;
                }
            }
        //매 경우마다 최댓값을 산출해서 result 도출
        result = max(result, cnt);
    }
    cout << result;
    return 0;
}