백준 2468번 - 안전 영역

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

문제가 길어서 처음에 무슨 문제인지 이해하는데 시간이 좀 걸렸다.
쉽게 생각하면 어떤 높이를 기준으로 해당 높이보다 큰 각 지점이 연결되어 있는 구역을 
하나의 영역이라고 했을 때, 각각의 높이마다 해당 영역의 개수가 달라질 것이다.
그리고 그 영역의 개수가 최대인 값을 구하면 된다.



영역의 개수를 구할 때 높이를 1부터 100까지 다 할 필요없이 주어진 높이들 중에 

가장 낮은 높이부터 가장 높은 높이까지 반복문을 실행하면 된다. 


가장 높은 높이가 10일때, 10까지 계산해도 물에 잠기지 않는 영역의 개수는 0이되고 
100까지  계산해도 물에 잠기지 않는 영역의 개수가 0이기 때문이다.



처음에 문제를 풀고 오답처리가 나서 뭐가 문제인지 고민해보았다.
문제의 조건에서 높이는 1부터 100까지라고 나와 있는데, 나는 높이가 1인 지점부터 생각해서 계산했다. 

즉 모든 지점의 높이가 1일때, 가장 낮은 높이인 1부터 시작해도 모두 잠기기 때문에 답을 0으로 계산했다.



문제가 안풀려서 이런 경우를 배제하고 최소한 한 개의 안전영역이 있다고 변수 값을 지정한 다음에 

가장 낮은 높이부터 높은 높이까지 계산했더니 패스됐다.



고민해봐도 잘 모르겠어서 일단 주석처리는 했는데..
왜인지는 모르겠지만.. 일단 문제에 접근하는 방법 자체는 맞는 것 같다.

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
int N;
int arr[100][100]={0};
int visited[100][100]={0};
 
void dfs(int y,int x,int height){
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=N || nx<0 || nx>=N)
            continue;
        
        if(arr[ny][nx]<=height || visited[ny][nx])
            continue;
        
        visited[ny][nx]++;
        dfs(ny,nx,height);
    }
    
}
 
int main(){
    
    cin>>N;
    
    int min_height=100,max_height=1;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&arr[i][j]);
            
            min_height=min(min_height,arr[i][j]);
            max_height=max(max_height,arr[i][j]);
        }
    }
    
    /*
    높이가 모두 1인 경우,
    0부터 물에 잠기지 않는 데 0값은 주어지지 않기 때문에 물에 잠기지 않는 경우의 수 없다
     
    if(max_height==1){
        cout<<0<<endl;
        return 0;
    }
     */
    
    
    int ans=1; //물에 잠기지 않는 영역의 최대 값
    for(int height=min_height;height<max_height;height++){
        
        memset(visited,0,sizeof(visited));
        
        int cnt=0; //물에 잠기지 않는 영역
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(arr[i][j]>height && !visited[i][j]){
                    visited[i][j]++;
                    cnt++;
                    dfs(i,j,height);
                }
            }
        }
        
        ans=max(ans,cnt);
    }
   
    cout<<ans<<endl;
    return 0;
}