[BOJ/2468번안전영역] c++ / BFS

문제

물에 잠기지 않는 안전영역의 최대 개수를 구하는 문제

-각 칸은 높이로 나타나져 있음

-높이는 1~100 이하의 수

 

생각

N이 100이하의 수여서 브루트포스 생각함

높이는 입력된 값중 가장 큰 값으로 제한을 두고, 맵에서 물에 잠기지 않는 지역이 나오면 BFS탐색

70프로에서 틀렸습니다 떠서 뭐가 문제인가 봤는데, 문제 조건에 모든 지역은 물에 잠기지 않을 수 있다가 있었음

ans = 0 에서 ans = 1로 고치니까 100 떴음 유유

 

문제풀이

1. 입력된 높이들 중 제일 큰 높이를 구함

2. 1번의 높이 값 만큼 BFS 탐색하면서, 영역 크기의 최댓값 구함

3. BFS 돌릴 때, vis 초기화 시켜줌

3-1. 들어온 높이보다 크고 방문한 적이 없는 지역이 나오면 푸쉬해줌 + 방문표시

-상하좌우에도 3번 과정 반복

4. 영역의 크기를 배열에 저장해둠

5. 최대 영역 크기 출력해줌

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define X first
#define Y second
int board[101][101];
int vis[101][101];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int N, cnt[101], h=0, ans=1;
void BFS() {
    queue<pair<int, int>> Q;
    int c = 0;

    for ( int i = 0; i < N; i++ ) // 초기화
        for ( int j = 0; j < N; j++ )
            vis[i][j] = 0;
        
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ )
            if ( board[i][j] > h && vis[i][j] == 0 ) {
                Q.push({i, j});
                vis[i][j] = 1;

                while(!Q.empty()) {
                    pair<int, int> cur = Q.front(); Q.pop();

                    for ( int dir = 0; dir < 4; dir++ ) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];

                        if ( nx < 0 || nx >= N || ny < 0 || ny >= N ) continue;
                        if ( board[nx][ny] <= h || vis[nx][ny] ) continue;

                        vis[nx][ny] = 1;
                        Q.push({nx, ny});
                    }
                }
                c++;
            }
    }
    cnt[h] = c;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < N; j++ )
            cin >> board[i][j];

    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < N; j++ ) 
            h = max(board[i][j], h);

    for ( ; h >= 1; h-- ) {
        BFS();
        ans = max(ans, cnt[h]);
    }

    cout << ans;
}