백준, BOJ, 2468번, 안전 영역 : C++ [CPP] ***

어렵진 않았다.

물 높이에 대해 조건만 만족시켜주면 된다.

 

 

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

2468번: 안전 영역

 

 

---

 

#맞는 풀이

 

#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <queue>

#define X first
#define Y second

using namespace std;

int M = INT_MIN;
int n;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int arr[100][100];
int visited[100][100];

int main(){
    cin >> n;
    int answer = 0;
    
    //노드 입력
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            cin >> arr[i][j];
            //최댓값 저장(물 높이를 위해서)
            if(M<arr[i][j]){
                M = arr[i][j];
            }
        }
    }
    
    
    //물의 높이 0부터 M까지 조사
    for(int h = 0; h<=M; h++){
        queue<pair<int,int>> q; //해당 높이에 쓰일 큐
        int safe = 0; // 해당 높이에서 안전지역 수
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(arr[i][j] <= h || visited[i][j] != 0) continue; // 물 높이보다 낮으면 침수되므로 조사 x + 방문했으면 조사 x
                q.push({i,j});
                safe++;
                while(!q.empty()){
                    auto cur = q.front();
                    q.pop();
                    //BFS로 확인
                    for(int dir = 0; dir<4; dir++){
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        
                        //범위체크(초과시 방문 x)
                        if(nx<0 || ny <0 || nx>=n || ny>=n) continue;
                        //방문했거나, 물의 높이보다 낮거나 같을경우 (방문 x)
                        if(visited[nx][ny] != 0 || arr[nx][ny] <= h) continue;
                        
                        q.push({nx,ny});
                        visited[nx][ny] = 1;//방문처리
                    }
                }
            
           }
        }
        
        if(answer <= safe){
            answer = safe;
        }
        
        //while문 돌리기 전 초기화
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                visited[i][j] = 0;
            }
        }
        
    }
    
    
    
    
    cout << answer;
    return 0;
}