Boj 2468 c++ 안전 영역

6모를 조졌다. 슬프다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int N;
int arr[101][101];
int safe[101][101];
int visited[101][101];

void BFS(int U, int V){
    queue<pair<int, int>> q;
    visited[U][V]=1;
    int dx[4]={0, 0, 1, -1};
    int dy[4]={1, -1, 0, 0};
    q.push({U, V});
    while(!q.empty()){
        U=q.front().first;
        V=q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx=dx[i]+U;
            int ny=dy[i]+V;
            if(nx<0 || ny<0 || nx>=N || ny>=N)
                continue;
            if(safe[nx][ny]==1 && !visited[nx][ny]){
                visited[nx][ny]=1;
                q.push({nx, ny});

            }
        }
    }
}

int main(){

  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);


  cin>>N;

  int Max=0, ans=0;

  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
        cin>>arr[i][j];
        Max=max(Max, arr[i][j]);
    }
  }
  for(int i=0; i<=Max; i++){
     for(int j=0; j<N; j++){
        for(int k=0; k<N; k++){
            visited[j][k]=0;
            safe[j][k]=0;
        }
     }
     for(int j=0; j<N; j++){
        for(int k=0; k<N; k++){
            if(arr[j][k]>i)
                safe[j][k]=1;
        }
     }
     int cnt=0;
     for(int j=0; j<N; j++){
        for(int k=0; k<N; k++){
            if(safe[j][k]==1 && !visited[j][k]){
                visited[j][k]=1;
                BFS(j, k);
                cnt++;
            }
        }
     }
     ans=max(ans, cnt);
  }
  cout<<ans;



}

빗물에 잠기지 않는 안전 영역의 최대 개수를 구하는 문제. 마찬가지로 연결요소의 개수와 풀이가 동일하다.