백준 2468 - 안전 영역

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

2468번: 안전 영역

문제 풀이

---

장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자.

이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. 

 

 

접근 방법

---

단지 구하기와 같은 유형입니다. 다만 수심이 변하기 때문에 잠길 때까지 bfs를 돌리고 나서 영역의 최대수를 구하면 됩니다~

여기서 물에 높이와 방문여부를 bfs 과정에서 같이 판단해도 되지만, 저는 복잡해서 memset으로 인해 초기화 후 visit 를 바꿔주면서 visit으로만 bfs를 진행했습니다!!

 

 

코드

---

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int land[101][101];
bool visit[101][101]={true,};
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
vector<int>ans;
void print(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<visit[i][j]<<" ";
        }
        cout<<"\n";
    }
}
void bfs(int y,int x){
    queue<pair<int,int> >q;
    q.push(make_pair(y,x));
    while(!q.empty()){
        int cury = q.front().first;
        int curx = q.front().second;
        q.pop();
        visit[cury][curx]=false;
        for(int i=0;i<4;i++){
            int ny = cury+dy[i];
            int nx = curx+dx[i];
            if((ny>=0&&nx>=0)&&(ny<n&&nx<n)){
                if(visit[ny][nx]==true){
                    q.push(make_pair(ny,nx));
                    visit[ny][nx]=false;
                }
            }
            else continue;
        }
    }
}
int main(){
   cin>>n;
   for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           cin>>land[i][j];
       }
   }
   int high=0;
   while(1){
       int count=0;
       memset(visit,true,sizeof(visit)/sizeof(bool));
       for(int i=0;i<n;i++){
           for(int j=0;j<n;j++){
                if(land[i][j]<=high) visit[i][j]=false;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(visit[i][j]){
                    count++;
                    bfs(i,j);
                    
                }
            }
        }
        ans.push_back(count);
        if(count==0) break;
        high++;
   }
   sort(ans.begin(),ans.end());
   cout<<ans[ans.size()-1]<<'\n';
}

funny algorithm $_$