인프런 커뮤니티 질문&답변

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 

// 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

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


////입력 : 
// 1. 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N (N은 2 이상 100 이하의 정수) 
// 2. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 
// 3. 높이는 1이상 100 이하의 정수이다.

////출력 : 
//첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

int n;
int arr[100][100]; 
int visited[100][100]; 
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
priority_queue<int> safeAreas; 

void dfs(int y, int x, int height){
    //방문처리       
    visited[y][x] = true; 
    //4방향 탐색 
    for(int i=0; i<4; i++){
        int nx = x + dx[i];  
        int ny = y + dy[i];

        //탐색 x 조건
        if( y < 0 || x < 0 || y >= n || x >= n ) continue; // out of bound 
        if( visited[ny][nx] ) continue; 
        if( arr[ny][nx] <= height ) continue; //물에 잠긴 지역 
        
        // 방문 
        dfs(ny,nx,height); 
    }
}

// find connected graphs
int getSafeAreaCnt(int height){
    memset(visited, 0, sizeof(visited));
    int connected = 0; 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[j][i] && arr[j][i] > height ){// 방문하지 않았고, safe area
                dfs(j,i, height);
                connected++; 
            }
        }    
    }
    return connected; 
}

int main() {
    //입력 
    cin >> n; 
    string input; 
    int maxHeight=0; 
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[j][i]; 
            maxHeight = max( maxHeight , arr[j][i] );    // 1. 높이의 max 값을 구한다. 
        }
    }
    
    for(int height=0; height <= maxHeight; height++){
        safeAreas.push( getSafeAreaCnt( height ) );
    }

    cout << safeAreas.top() << '\n'; 
}

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

안녕하세요 큰돌님. segmentation fault 나는데 어디서 나는지 잘 모르겠습니다 ㅠ

priority queue 때문인 거 같은데 한 번 더 확인 해보겠습니다.