[백준/C++] 2468번 - BFS

문제 - 2468번

문제는 위와 같다.

아무 지역도 물에 잠기지 않을 수도 있다는 점을 처리하지 않아서

테스트 케이스는 맞았으나 정답은 틀렸다는 결과를 받았다.

 

풀이와 생각의 흐름

우선 연결된 영역의 개수를 찾는다는 점에서 BFS를 이용함을 알 수 있다. 

(BFS 문제를 많이 풀다보면 적어도 이 문제가 BFS를 활용하는구나는 알 수 있다. -> 나도 첨에는 몰랐었다...ㅠㅠ)

물에 잠기지 않는 안전 영역의 개수가 최대인 경우를 다 조사해서 출력하는 문제이다.

 

그러면 (1)비의 정보마다 BFS를 진행하면 되고,

각 BFS를 통해서 찾은 영역의 개수와 (2)기존의 개수를 비교해서 큰 값을 유지하도록 갱신하면 된다.

 

(1) 비의 정보는 어디서,,?

비의 양에 따라서 BFS를 진행해야하는데, 비의 정보가 문제에 없다.

그래서 처음에 값을 입력받을 때 비의 양의 최소와 최대값을 찾아서 iMin, iMax 변수에 넣어놨다.

그리고 iMin ~ iMax까지 BFS를 반복했다. (3중 반복문이라 맘에 들진 않았지만,,,)

 

(2) 아무 영역도 물에 잠기지 않는 경우가 있다는 조건!

나의 코드에서 정답을 담고 있는 변수이자, 최대값으로 갱신되는 변수가 iCnt인데,

이 값의 초기값을 1로 설정하지 않아서 처음에 틀렸다.

 

따라서 아무것도 잠기지 않아서 다 연결된 경우 1이 최소값이 되어야 한다.

그래서 iCnt는 1로 초기화하여 갱신해줘야 한다. 

 

* 매번 BFS를 진행해야하니 iVisited 배열을 계속 초기화 해줘야한다는 것만 잘 해주면

보통의 BFS 문제처럼 풀 수 있을 것 같다! 

 

 

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int iN, iCnt=1, iSize;
int iBoard[101][101];
int iVisited[101][101]={0,};
int iMin = 100, iMax=0;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void resetVisited(){
    for (int i=0;i<iN;++i){
        fill(iVisited[i],iVisited[i]+iN,0);
    }
}

void bfs(int i,int j, int value){
    queue<pair <int, int>> q;
    q.push({i,j});
    iVisited[i][j]=1;
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for (int i=0;i<4;++i){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if (nx<0 || ny <0||nx>=iN || ny>=iN) continue;
            if (iVisited[nx][ny] || iBoard[nx][ny]<=value) continue;
            q.push({nx,ny});
            iVisited[nx][ny]=1;
        }
    }
}
int main(){
    cin >>iN;
    for (int i=0;i<iN;++i){
        for (int j=0;j<iN;++j){
            cin>>iBoard[i][j];
            if (iBoard[i][j]>iMax) iMax= iBoard[i][j];
            if (iBoard[i][j]<iMin) iMin = iBoard[i][j];
        }
    }
    for (int value=iMin; value<=iMax;++value){
        resetVisited();
        iSize = 0;
        for (int i=0;i<iN;++i){
            for (int j=0;j<iN;++j){
                if (iBoard[i][j]<=value){
                    iVisited[i][j]=1;
                }
                if (iVisited[i][j]==0){
                    bfs(i,j, value);
                    iSize++;
                }
            }
        }
        iCnt = max(iCnt, iSize);
    }
    cout<<iCnt;
}