BOJ2468 : 안전영역 (Silver 1)

 

우선 나는 make_safezone으로 safe_zone 배열에 침수되는지 아닌지를 저장해주었다.

rain_height보다 높이가 높으면 1, 낮거나 같으면 0으로 영역이 1로 가시적으로 보이게 만들어줌

 

그리고 나서 count_safezone 해서 만들어 둔 safezone의 영역 크기를 DFS를 활용해 세어주었다.

 

이 과정을 rainheight 0부터 100까지 반복해 최댓값을 찾아주면 끝!

 

 

#include <stdio.h>
#include <iostream>
#include <string.h>

using namespace std;

int height[100][100] = {0,};
int safe_zone[100][100] = {0,};


int N = 0; 

void make_safezone(int rain_height);
int count_safezone();
void DFS(int a, int b);

int main(){
   ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
   int rain_height = 0;
   int i, j =0;
   int m, n ;
   int max_safezone = 0;
   cin >> N;
   
   for(i=0; i<N; i++){
    for(j=0; j<N; j++){
        cin >> height[i][j];
    }
   }
    for(rain_height=0; rain_height<=100; rain_height++){
        make_safezone(rain_height);
                // cout << "\n safezone \n";
                // for(n=0; n<N; n++){
                //     for(m=0;m<N;m++){
                //         cout<<safe_zone[n][m]<<" ";
                //     }
                //     cout <<"\n";
                // }
        int num_safezone = count_safezone();
        if (max_safezone < num_safezone)
            max_safezone = num_safezone;
    }
    cout << max_safezone;
}

void make_safezone(int rain_height){
    int i, j = 0;

    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            if(height[i][j] > rain_height)
                safe_zone[i][j] = 1;
            else
                safe_zone[i][j] = 0;
        }
    }
}

int check[100][100] = {0,};
int count_safezone(){
    int i, j=0;
    int n,m;
    int count = 0;
    memset(check, 0, sizeof(check));
    for(i = 0; i<N; i++){
        for(j=0; j<N; j++){
            if(safe_zone[i][j] && !check[i][j]){
                DFS(i, j);
                // cout << "\n DFS CHECK \n";
                // for(n=0; n<N; n++){
                //     for(m=0;m<N;m++){
                //         cout<<check[n][m]<<" ";
                //     }
                //     cout <<"\n";
                // }
                count ++;
            }
        }
    }
    return count;
}

void DFS (int a, int b){
    if(check[a][b]==1 || safe_zone[a][b] == 0){
        return;
    }
    check[a][b] = 1;

    if(b<N-1) DFS(a, b+1);
    if(a<N-1) DFS(a+1, b);
    if(a>0) DFS(a-1,b);
    if(b>0) DFS(a,b-1);
}

 

나의 첫 번째 실수 - DFS if 문 조건 실수

 

이건 걍 내가 똥멍청이 ㅠㅠ

 

두 번째 실수 - 비가 안 올 수도 있다는 사실을 캐치하지 못하였다

비가 안올수도 있어서 rain_height의 시작이 0이였어야 했는데, 1부터 해서 한참 해맴 ㅠㅠ

다행히 인터넷에 바로 찾으니까 떠서 고쳤다

 

 

 

고난과 역경..