[백준] 빙산 (2573)

2573번: 빙산

출처: pixbay

맨 처음 문제를 봤을 때, 얼음이 녹는다는 표현을 보고 예전에 풀었던 치즈가 생각나긴 했는데 치즈는 머리를 써야 푸는 문제였다면, 이 문제는 머리보다는 손을 더 많이 써야 하는 문제입니다.

 

각 칸의 얼음은 1년 마다 인접한 네 방향(동서남북) 중 바다(배열값이 0)인 갯수만 큼 녹아내려 0이되면 바다가 됩니다. 문제의 목표는 한 덩이의 얼음이 주어졌을 때, 두덩이 이상으로 변하기 까지의 시간을 구해야 합니다. 단, 동시에 전부 없어지면 0을 출력해야 합니다.

 

풀이는 간단합니다. 얼음이 쪼개지거나, 동시에 없어질 때 까지 얼음 덩어리의 갯수를 파악하고, 얼음 덩어리에 포함이 되는 얼음들을 녹이는 과정을 되풀이 하면 됩니다. 대신 이를 구현하는 과정이 복잡합니다.

1. BFS 전체탐색을 통해 얼음 덩어리를 찾는다. 이때 얼음 덩어리가 2개 이상임이 발견되면, 현재 진행된 시간을 출력하고, 하나도 없으면 0을 출력한다.
2. 1번을 통해 얻어진 얼음들(i,j)을 인접해 있는 바다의 갯수만큼 녹인다.
3. 진행 시간을 1 올린다.

 

코드보기(C++)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool in_range(int n, int m, int i, int j) {
    return (0 <= i && i < n) && (0 <= j && j < m);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, m, g[300][300];
    int di[4] = {0,0,1,-1};
    int dj[4] = {1,-1,0,0};
    vector<pair<int, int>> e;
    queue<pair<int, int>> q;
    vector<int> melt;
    bool visited[300][300];

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> g[i][j];

    int ans = 0;
    while(true) {
        int cnt = 0;
        
        e.clear();
        melt.clear();
        for(int i = 0; i < n; i++)
            fill_n(visited[i], m, false);
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(g[i][j] > 0 && !visited[i][j]) {
                    // 이미 빙하가 하나 있는 경우
                    if(cnt == 1) {
                        cout << ans << '\n';
                        return 0;
                    }
                    cnt++;
                    q.push({i,j});
                    visited[i][j] = true;
                    // 빙하 조사
                    while(!q.empty()) {
                        int si = q.front().first, sj = q.front().second;
                        int melt_cnt = 0;
                        q.pop();
                        e.push_back({si, sj});

                        for(int k = 0; k < 4; k++) {
                            int ni = si + di[k], nj = sj + dj[k];
                            if(!in_range(n,m,ni,nj)) continue;
                            if(g[ni][nj] <= 0) {
                                melt_cnt++;
                                continue;
                            }
                            if(visited[ni][nj]) continue;
                            visited[ni][nj] = true;
                            q.push({ni, nj});
                        }

                        melt.push_back(melt_cnt);
                    }
                }
            }
        }

        if(cnt == 0) {
            // 동시에 전부 다 녹음
            cout << 0 << '\n';
            return 0;
        }

        // 녹이기
        for(int k = 0; k < (int)e.size(); k++)
            g[e[k].first][e[k].second] -= melt[k];
        ans++;
    }
    
    return 0;
}