백준(BOJ) 2468 안전 영역 **

# DFS

어렵지 않은 DFS문제이다.

크기를 고려했을때 모든 홍수의 값에 대해서 돌려도 충분히 돌아가기 때문에 금방 풀 수 있다.

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 105
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

int n,arr[MAX][MAX],mi=INF,mx=0,ans=1;
int dy[4]={0,0,1,-1},dx[4]={1,-1,0,0};
bool map[MAX][MAX];

void dfs(int y,int x)
{
    for(int i=0;i<4;i++)
    {
        int ty=y+dy[i],tx=x+dx[i];
        if(map[ty][tx]==true)
        {
            map[ty][tx]=false;
            dfs(ty,tx);
        }
    }
}
// 연결된 안전영역을 지워준다.

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            scanf("%d",&arr[i][k]);
    // 입력을 받는다.
    
    for(int i=1;i<=100;i++)
    {
        int tmp=0;
        memset(map,false,sizeof(map));
        for(int p=1;p<=n;p++)
            for(int q=1;q<=n;q++)
                map[p][q]=arr[p][q]<=i?false:true;
        // 홍수의 크기 이하의 경우 false로 해준다.
        for(int p=1;p<=n;p++)
            for(int q=1;q<=n;q++)
                if(map[p][q]==true)
                {
                    dfs(p,q);
                    tmp++;
                }
        // dfs()가 돌아갈 때 마다 안전영역의 수를 증가시킨다.
        ans=ans<tmp?tmp:ans;
    }
    printf("%d",ans);
    return 0;
}