[BOJ/2573번빙산] c++ / BFS

문제

한 덩어리로 이루어진 빙산이 두덩어리 이상으로 나뉠 때까지 걸리는 최소 년을 구하는 문제

-빙산은 1년에 상하좌우로 인접한 바다의 개수만큼 녹아내림

-빙산이 모두 녹아내리면 0을 출력함

 

생각

빙산 덩어리의 개수가 2개 이상이 될 때까지 또는 빙산이 모두 녹을 때 BFS 탐색해야겠다 생각함

전자의 답은 BFS 돌린 횟수이고, 후자의 답은 0이 됨

 

문제풀이

1.빙산이 나오면 BFS 탐색

2.빙산 상하좌우에 바다가 있다면, 빙산-- 해줌 ( 빙산이 1보다 클 때 )

/ 주의: 같은 년도에 빙산이었다가 바다가 된 바다는 취급하지 않음 ( 방문표시 확인 )

2-1.빙산 상하좌우에 방문하지 않은 빙산이 있다면, 방문표시  + 큐에 푸쉬

3.빙산 덩어리의 개수를 구하는 함수 실행

3-1.덩어리의 개수가 2개 이상이라면 ck = 1 표시

4.BFS 실행만큼 result++ 해줌

5.만약 반복문을 모두 돌아도 ck = 1가 아니라면, 0을 출력

5-1.그렇지 않다면 반복문 중간에 result 출력

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int N, M, cnt=0, result=0, ck=0;
int board[301][301];
int vis[301][301];
int Icenum();
void BFS(int x, int y) {
    queue<pair<int, int>> Q;
    vis[x][y] = 1;
    Q.push({x, y});

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

        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 >= M ) continue;
            if ( board[nx][ny] == 0 && board[cur.X][cur.Y] > 0 && !vis[nx][ny] )
                board[cur.X][cur.Y]--;

            if ( board[nx][ny] && !vis[nx][ny] ) {
                vis[nx][ny] = 1;
                Q.push({nx, ny});
            }
        } 
    }
    memset(vis, 0, sizeof(vis));
    if ( Icenum() > 1 )
        ck = 1; 
}
int Icenum() {
    queue<pair<int, int>> Q;
    cnt = 0;
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( board[i][j] == 0 || vis[i][j] ) continue;
            cnt++;
            vis[i][j] = 1;
            Q.push({i, j});

            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 >= M ) continue;
                    if ( !board[nx][ny] || vis[nx][ny] ) continue;

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

    cin >> N >> M;
    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < M; j++ )
            cin >> board[i][j];
    
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( board[i][j] ) {
                result++;
                memset(vis, 0, sizeof(vis));
                BFS(i, j);
                if ( ck == 1 ) {
                    cout << result;
                    break;
                }
            }
        }
        if ( ck == 1 )
            break;
    }

    if ( ck == 0 )
        cout << 0;
}