[백준/c++] 2468번: 안전 영역

 

 

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

2468번: 안전 영역

 

 

비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다.

물에 잠기지 않는 안전 영역 == 물에 잠기지 않는 지점이 상||하||좌||우로 인접하고 크기가 최대인 영역이다.

이 문제에서 가장 큰 어려움은 안전 영역에 대한 이해였다. 생각해보면 쉬운데 왜 이해하지 못했는지 모를..

 

 

좌측 그림은 비가 내려서 높이가 4 이하인 곳은 물이 잠긴 것을 의미하는데, 여기서 노란색 덩어리의 개수가 5개로, 안전 영역은 5개이다.

우측 그림은 높이가 6 이하인 곳이 물에 잠겨 핑크색 덩어리의 갯수 4개가 안전 영역의 개수다.

 

문제에서 비가 얼마만큼 올지 알려주지 않았기 때문에 비가 오지 않은 (0)부터 최대 높이-1까지 해주면 되는데, 처음엔 1부터 maxR-1 까지라고 해서 틀렸다. 비가 오지 않는 경우가 있기 때문에 꼭 0부터 시작해줘야 한다.

 

이제, 순서대로 진행해주면 된다.

 - Raining() : 비를 내리게 해서 높이를 저장한 배열을 변화시켜주고 (물에 잠기면 0으로 바꿔줌)

 - 비에 잠기지 않고, 방문하지 않은 곳이면 BFS()를 돌려서 안전 영역의 개수를 카운팅

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAX 102
using namespace std;
int n, arr[MAX][MAX], maxR = -1;
bool visited[MAX][MAX];
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void Raining(int x){
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) visited[i][j] = false; //초기화
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(arr[i][j] <= x) arr[i][j] = 0;
}

void bfs(int sx, int sy){
    queue<pair<int, int>> q;
    q.push({sx, sy});
    visited[sx][sy] = true;
    
    while(!q.empty()){
        int x = q.front().first; int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            
            if(dx < 0 || dy < 0 || dx >= n || dy >= n) continue;
            if(visited[dx][dy] || arr[dx][dy] == 0) continue;
            
            visited[dx][dy] = true;
            q.push({dx, dy});
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int answer = 0;
    
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> arr[i][j];
            maxR = max(maxR, arr[i][j]);
        }
    }
        
    for(int i=0; i<maxR; i++){
        int cnt = 0;
        //비 내리기
        Raining(i);
        
        //안전 영역 카운팅
        for(int i=0; i<n; i++){ //비가 전혀 오지 않을 경우가 있으므로 0부터 시작
            for(int j=0; j<n; j++){
                if(arr[i][j] != 0 && !visited[i][j]){
                    bfs(i, j);
                    cnt++;
                }
            }
            answer = max(answer, cnt);
        }
    }
    
    cout << answer << '\n';
    return 0;
}