[BOJ] 2573. 빙산

https://www.acmicpc.net/problem/2573

2573번: 빙산

BFS를 이용해서 푸는 문제이다.

 

인접한 칸이 바다인 경우에는 그 개수를 세주어서 빙산의 높이에서 빼주면 된다.

바다가 아닌 빙산인 경우에는 큐에 넣어주고 해당 빙산에 대해서도 탐색을 이어가면 된다.

 

 

BFS는 연결된 모든 칸을 방문하기 때문에 연결되지 않은 칸에 방문하기 위해서는 BFS를 새로 시작하여야 한다.

즉, bfs횟수가 1회일 때는 아직 모두 연결되어 있는 한 덩어리라는 뜻이므로 계속 시간을 늘려가며 bfs를 진행하고

BFS 횟수가 1번이 넘을 때는 빙산이 두 덩어리 이상이 됐음을 의미하므로 그때 시간을 출력해주고 탐색을 종료한다.

 

 

만약 다 녹았는데 빙산이 분리되지 않은 경우를 처리하기 위해서는 flag 변수를 둬서 bfs탐색이 한 번도 일어나지 않은 경우에 0을 출력해주고 종료하도록 해줬다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m;
int map[300][300];
bool check[300][300];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (check[nx][ny]) continue;
 
            //인접한 칸이 바다인 경우 cnt증가
            if (map[nx][ny] == 0) {
                cnt++;
            }
            else {
                //빙산인 경우에는 큐에 넣어주고 계속 탐색
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
            
        }
 
 
        //인접해 있는 바다의 수만큼 높이 줄어든다.
        map[x][y] -= cnt;
        //0보다 작아지지는 않는다.
        if (map[x][y] < 0) map[x][y] = 0;
 
    }
 
}
 
void solve() {
 
    int time = 0;
    while (true) {
        int cnt = 0;
        bool flag = false;
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                //바다인 경우 continue
                if (map[i][j] == 0) continue;
                //이미 방문한 경우
                if (check[i][j]) continue;
 
                //빙산이 아직 있다.
                flag = true;
                bfs(i, j);
 
                //빙산의 덩어리 수
                cnt++;
            }
        }
 
        //전부 다 녹을 때까지 두덩어리 이상으로 분리되지 않는 경우
        if (!flag) {
            cout << 0 << '\n';
            return;
        }
 
 
        //두 덩어리 이상이 되었을 경우 시간을 출력하고 return(종료)
        if (cnt > 1) {
            cout << time << "\n";
            return;
        }
 
 
        //시간 증가
        time++;
 
        memset(check, false, sizeof(check));
    }
 
    
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    solve();
 
    return 0;
}