[백준] 2468 안전영역

솔직히 처음 문제를 읽었을 때 N이 비가 내리는 양을 포함하는 줄 알고 풀었다.

신기하게 문제에서 제공해 주는 예제들이 모두 통과가 되었다 ㅋㅋㅋ

 

그리고 제출했더니.; 틀렸습니다 (눈물..)

 

문제를 조금 꼼꼼하게 읽어보니 안전영역이 덩어리 지는 최대의 개수를 구하는 것이었다...!!

바로 수정..

 

어렵지 않고 쉬운 문제였다.

 

□ 소스코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input2468(101,vector<int>(101,0));
vector<vector<bool>> check2468(101,vector<bool>(101,false));
int count2468 = 0;
int rain2468 = 0;
queue<pair<int, int>> q2468;

void bfs2468(int N,int x, int y){
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    
    while (!q2468.empty()) {
        int frontX = q2468.front().first;
        int frontY = q2468.front().second;
        q2468.pop();
        
        for(int i=0;i<4;i++){
            int mx = frontX + dx[i];
            int my = frontY + dy[i];
            
            if(mx<1 || my <1 || mx > N || my >N)
                continue;
            
            if(input2468[mx][my] > rain2468 && !check2468[mx][my]){
                q2468.push({mx,my});
                check2468[mx][my] = true;
            }
        }
    }
}

void safeArea2468(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin>>N;
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            int a; cin>>a;
            input2468[i][j] = a;
            rain2468 = max(a,rain2468);
        }
    }

    while(1){
        int count = 0;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(input2468[i][j] > rain2468 && !check2468[i][j]){
                    q2468.push({i,j});
                    check2468[i][j] = true;
                    bfs2468(N, i, j);
                    count++;
                }
            }
        }
        
        fill(check2468.begin(), check2468.end(), vector<bool>(101,false));
        count2468 = max(count2468, count);
        if(rain2468 == 0)
            break;
        rain2468--;
        
    }
    
    cout<<count2468<<"\n";
}

 

□ 반례

3
0 1 1
0 0 1
0 1 1
ANS: 1