2468번 - 안전 영역

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

2468번: 안전 영역

 

비가 안 올 때, 즉 check 함수를 호출할 때 i가 0일 때도 고려했어야 했는데 안 해서 틀렸다. 

#include <iostream>
#include <cstring>
using namespace std;
int N;
int Map[101][101];
int Check[101][101];
bool isVisited[101][101];
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};
int MAX = 0, ans = 0, cnt = 0;
bool isPossible(int row, int col)
{
    if(row < 0 || row >= N || col < 0 || col >= N)
        return false;
    return true;
}
void dfs(int row, int col)
{
    isVisited[row][col] = true;
    for(int i=0; i<4; i++)
    {
        int ny = row + dy[i];
        int nx = col + dx[i];
        if(false == isPossible(ny,nx) || 0 == Check[ny][nx] || true == isVisited[ny][nx])
            continue;
        dfs(ny, nx);
    }
}
void check(int height)
{
    //초기화
    memset(Check, 0, sizeof(Check));
    memset(isVisited, false, sizeof(isVisited));
    cnt = 0;

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            //비에 잠긴다면 -> 0
            if(Map[i][j] <= height)
                Check[i][j] = 0;
            //아니면 -> 건물의 높이 
            else
                Check[i][j] = Map[i][j];
        }
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            //잠기지 않았고 방문하지 않았으면
            if(Check[i][j] != 0 && false == isVisited[i][j])
            {
                cnt++; //안전지대 +1
                dfs(i, j); //dfs 실행
                
                //dfs가 다 끝나고 cnt가 기존 ans보다 많으면 ans update
                if(cnt > ans)
                    ans = cnt;
            }
        }
    }
}
int main()
{
    cin >> N;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            int tmp;
            cin >> tmp;
            Map[i][j] = tmp;

            if(MAX < tmp)
                MAX = tmp;
        }
    }
    //비 내림
    for(int i=0; i<=MAX; i++)
    {
        check(i);
    }
    cout << ans << '\n';
    return 0;
}