(C++) - 백준(BOJ)코딩 2468번 : 안전 영역 답

www.acmicpc.net/problem/2468

2468번: 안전 영역

비의 높이를 1씩 증가시키면서 bfs로 안전영역의 개수를 센 후 가장 큰 값이 답인 brute force 문제였습니다.

 

풀이방법

 1. 잠기는 물의 높이를 0부터 100까지라고 설정한 후 정한 물의 높이보다 높은 지역만 안전영역으로 지정하고 이를 값 1이라고 가정합니다.

 2. 안전영역이 있다면 이와 인접한 안전영역을 check하기 위해 모든 안전영역을 검사하며 check가 안되어 있다면 bfs를 시행합니다. 따라서 bfs 호출 개수가 곧 안전영역의 개수가 됩니다.

 3. 모든 담기는 물의 높이에 대해 안전 영역을 만든 후 안전 영역에 대해 bfs를 호출하고 나오는 결과 값들의 max가 곧 답이 됩니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};

int area[101][101];
int safeArea[101][101];
int check[101][101];
int n, ans;

void immerseArea(int n, int waterHeight){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(waterHeight < area[i][j]) safeArea[i][j] = 1;
        }
    }
}

void bfs(int i,int j){
    queue <pair<int,int>> q;
    q.push({i,j});
    check[i][j] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >=n) continue;
            if(!safeArea[nx][ny]) continue;
            if(!check[nx][ny]){
                check[nx][ny] = 1;
                q.push({nx,ny});
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> area[i][j];

    for(int waterHeight = 0; waterHeight <= 100; waterHeight++){
        memset(safeArea,0,sizeof(safeArea));
        memset(check, 0, sizeof(check));
        immerseArea(n, waterHeight);
        int cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(!check[i][j] && safeArea[i][j]){
                    bfs(i,j);
                    cnt++;
                }
            }
        }
        ans = max(ans,cnt);
    }
    cout << ans <<'\n';
}