(매일 BOJ) C++ 2468번 안전 영역

이번 문제는 2468번 안전 구역이다

문제 개요

문제 링크: 백준 2468번 - 안전 영역

N×N 크기의 지도에서 각 칸의 높이는 0 이상 100 이하
비가 내리면 일정 높이 이하의 영역은 물에 잠기게 되고, 물에 잠기지 않는 영역들을 안전 영역으로 정의하고
비가 내린 후, 각 높이에 대해 물에 잠기지 않는 영역의 개수를 구하는 문제이다.

접근법

이 문제는 각 높이별로 물에 잠기지 않는 영역을 찾아 그 개수를 계산하는 문제다.
단지의 개수를 세는 알고리즘을 사용하여, 각 높이에 대해 안전 영역을 구하는 방식으로 접근하였다

1. 입력 받기
   • N×N 크기의 지도와 각 칸의 높이를 입력함
2. 각 높이에 대해 안전 영역 개수 계산
   • 각 높이에 대해 해당 높이보다 작은 값은 물에 잠기므로, 그 높이 이상인 부분만 연결된 안전 영역으로 취급
3. DFS를 이용한 영역 탐색
   • 4방향(상, 하, 좌, 우)으로 연결된 집을 DFS로 탐색하여, 하나의 단지를 구분
4. 결과 출력
   • 각 높이에 대해 구한 안전 영역의 개수 중 최대값을 출력

작성코드

#include <bits/stdc++.h>
using namespace std;

void DFS (vector<vector<int>> & arr, vector<vector<bool>> & visited, int x, int y, int);
int fourway_x[4] = {0,0,1,-1};
int fourway_y[4] = {1,-1,0,0};
int N;


int main (void){
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> N;
    vector<vector<int>> arr(N,vector<int>(N));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            int num;
            cin >> num;
            arr[i][j] = num;
        }
    }

    vector<vector<bool>> visited(N,vector<bool>(N,false));
    int count_max = 0;
    int count = 0;

    for(int i = 0; i <= 100; i++){
        
        for(int j = 0; j < N; j++){
            fill(visited.begin(), visited.end(), vector<bool>(N, false));
        }

        count = 0;
        for(int x = 0; x < N; x++){
            for(int y = 0; y < N; y++){
                if(arr[x][y] > i && !visited[x][y]){
                    DFS(arr,visited,x,y,i);
                    count += 1;
                } 
            }
        }
        if(count > count_max) count_max = count;

    }
    cout << count_max;

    return 0;
}

void DFS (vector<vector<int>> & arr, vector<vector<bool>> & visited, int x, int y, int hight){
    visited[x][y] = true;

    int next_x,next_y;
    for(int i = 0; i < 4; i++){
        next_x = x + fourway_x[i];
        next_y = y + fourway_y[i];

        if(next_x >= 0 && next_y >= 0 && next_x < N && next_y < N && !visited[next_x][next_y] && arr[next_x][next_y] > hight){
            DFS(arr,visited,next_x,next_y,hight);
        }
    }
}