백준 2468 - 안전영역 - DFS

문제

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

풀이전략

1. 이 문제같은경우 비의 양에 따른 모든 경우의 수를 계산하여야하기 때문에 따로 체크배열을 만들어서 케이스에 맞게 확인해주어야한다.
2. N은 100이하이므로 시간과 공간은 충분하다. 충분히 DFS로 계산하면 된다.
3. dx, dy를 만들어주어 상하좌우를 확인한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
// 순서대로 위 오른 아래 왼
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int a[102][102];
// 체크배열
bool ch[102][102];
// 결과
int res = 1;
// 내리는 비의 양
int standKey = 0;
void DFS(int r, int c){
    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];
		// 내리는 비보다 값이 커야 안전지대이다.
        // 그 안전지대끼리 DFS를 한다. 
        if( !ch[rr][cc] && a[rr][cc] > standKey){
            ch[rr][cc] = true;
            DFS(rr,cc);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    int myMin = 2147000000, myMax = -2147000000;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> a[i][j];
            // input에 가장 작은 값부터 가장 큰값까지 순차적으로 비의양을 계산해야한다. 
            if(a[i][j] > myMax) myMax = a[i][j];
            if(a[i][j] < myMin) myMin = a[i][j];
        }
    }
    for(standKey=myMin; standKey<=myMax; standKey++){
        memset(ch, false, sizeof(ch));
        int cnt = 0;
        
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if( !ch[i][j] && a[i][j] > standKey){
                    ch[i][j] = true;
                    DFS(i, j);
                    cnt++;
                }
            }
        }
        if(cnt > res) res = cnt;
    }
    cout<<res<<endl;


    return 0;
}

소감

결국 비의 양보다 큰 값들을 찾아야하는 것만 새로울 뿐 그동안의 DFS문제와 거의 비슷하였다.