2468 안전 영역

문제 링크

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

풀이

처음에 출력할 값 ans를 1로 초기화 해놓고 시작한다. 1~최고지점 높이까지 비가 오는 경우에 대해 반복문을 돌며 각 수위에 대한 안전 영역의 개수를 세면 된다. 반복문을 돌며 수위보다 높은 칸이면서 visit이 false인 칸을 찾으면 안전 영역의 개수를 +1 하고 bfs를 통해 인접 칸들의 visit을 업데이트 한다. visit은 수위가 달라질 때마다 전부 false로 업데이트한다. 만약 해당 수위에 대해 구한 안전 영역의 개수가 기존의 개수보다 많으면 ans를 업데이트한다.

C++ 코드

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

int N;
int arr[100][100];
int ans = 1;
bool visit[100][100];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs(int x, int y, int rain){
    queue<pair<int,int>> q;
    q.push(make_pair(x, y));
    visit[x][y] = true;
    
     while(!q.empty()){
         pair<int, int> p = q.front();
         q.pop();
         for(int i=0; i<4; i++){
             int nx = p.first+dx[i];
             int ny = p.second+dy[i];
             if(!visit[nx][ny] && arr[nx][ny] > rain && 0<=nx && nx<N && 0<=ny && ny<N){
                 q.push(make_pair(nx, ny));
                 visit[nx][ny] = true;
             }
         }
     }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N;
    
    int max = 0;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>arr[i][j];
            if(max < arr[i][j])
                max = arr[i][j];
        }
    }
    
    for(int n=1; n<max; n++){
        int safe = 0;
        memset(visit, false, sizeof(visit));
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(arr[i][j] > n && !visit[i][j]){
                    bfs(i, j, n);
                    safe++;
                }
            }
        }
        if(safe > ans)
            ans = safe;
    }
    
    cout<<ans<<endl;
    
    return 0;
}