[DFS] 백준 2468번 - 안전영역 (정답률 33%)

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

백준 DFS 연습문제다.

보통 이런 문제에 대해 한 가지 경우에 대한 문제는 50~60%정도 정답률을 보이지만,

이 문제와 같이 다양한 경우에 대해 dfs 탐색을 요구하는 문제는 정답률이 약 30%대로 떨어진다.

 

전자의 문제와 다를 바 없이, 매 조건에 대해 새롭게 방문여부 벡터를 초기화해주고, 조건에 맞게 세팅을 한 뒤에 dfs 탐색을 똑같이 하면 쉽게 풀 수 있다.

 

아래는 제출한 코드 (16ms)

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int N;
int maxheight = -1;
int answer = -INF;
int cur_safety_fields = 0;
vector<vector<int> > height;
vector<vector<bool> > check;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void reset(){
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            check[i][j] = false;
}
 
void dfs(int r, int c){
    for (int i = 0; i < 4; i++){
        int nr = r + direction[i].dr;
        int nc = c + direction[i].dc;
        if (nr >= 0 && nr < N && nc >= 0 && nc < N){
            if (!check[nr][nc]){
                check[nr][nc] = true;
                dfs(nr, nc);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    height.assign(N, vector<int>(N, 0));
    check.assign(N, vector<bool>(N, 0));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> height[i][j];
            if (height[i][j] > maxheight)
                maxheight = height[i][j];
        }
    }
    
    for (int limit = 0; limit <= maxheight; limit++){
        //limit 이하 지역 모두 침수, 안전영역 구하기.
 
        // 1. limit 이하 지역 모두 침수
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (height[i][j] <= limit){
                    check[i][j] = true;
                }
            }
        }
 
        // 2. 이제 안전영역의 개수를 구해보자.
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (!check[i][j]){
                    check[i][j] = true;
                    dfs(i, j);
                    cur_safety_fields++;
                }
            }
        }
        answer = max(answer, cur_safety_fields);
        cur_safety_fields = 0;
        reset();
    }
    cout << answer << '\n';
    return 0;
}