[C++] BAEKJOON 2468 안전 영역

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

2468번: 안전 영역

dfs 를 사용하여 문제를 해결하였습니다.

• 최대 높이 maxH 측정
• 높이 0 부터 maxH 까지 각 경우를 고려
• visited 배열을 만들어서 물에 잠기는 지역과 잠기지 않은 지역을 표시
• dfs 를 이용하여 안전영역의 개수 계산
• 매 높이 마다 안전영역의 개수를 계산하여 최대값 출력

#include <iostream>

using namespace std;

int board[101][101];
int visited[101][101];

int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};

void dfs(int r, int c, int n){
    
    visited[r][c] = -1;
    
    for (int i=0;i<4;i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (0<=nr && nr<n && 0<=nc && nc<n){
            if (visited[nr][nc] == 0)
                dfs(nr,nc,n);
        }
    }
}

int main(int argc, const char * argv[]) {
    
    int n;
    cin >> n;
    
    int maxH = 0;
    
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cin >> board[i][j];
            if (board[i][j] > maxH)
                maxH = board[i][j];
        }
    }

    
    int safeNumMax = 0;
    
    for (int h=0;h<=maxH;h++){
        // visited 초기화
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                // 물에 잠기면 -1 아니면 0
                if (board[i][j] <= h)
                    visited[i][j] = -1;
                else
                    visited[i][j] = 0;
            }
        }
        
        int safeNum = 0;
        
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (visited[i][j] == 0){
                    
                    safeNum++;
                    dfs(i,j,n);
                }
            }
        }
        
        safeNumMax = max(safeNumMax, safeNum);
    }
    
    cout << safeNumMax << "\n";
  
    return 0;
}