[BOJ / C++] 빙산 (BFS)

문제링크: https://www.acmicpc.net/problem/2573

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int iceCnt(vector<vector<int>>& board, int n, int m) {
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    queue<pair<int, int>> Q;

    int 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;

            vis[i][j] = true;
            Q.push({i, j});
            cnt++;
            while (!Q.empty()) {
                auto cur = Q.front(); Q.pop();
                int x, y;
                tie(x, y) = cur;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (board[nx][ny] <= 0 || vis[nx][ny] == true) continue;
                    Q.push({nx, ny});
                    vis[nx][ny] = true;
                }
            }
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> board(n, vector<int>(m, 0));

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

    int year = 0;
    while (true) {
        if (iceCnt(board, n, m) >= 2) break;
        
        vector<vector<int>> tmp(board);
        year++;
        bool allmelt = true;
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                if (tmp[x][y] >= 1) {
                    allmelt = false;
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];
                        
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (tmp[nx][ny] == 0) {
                            if (board[x][y] == 0) continue;
                            else board[x][y] -= 1;
                        }
                    }
                }
            }
        }
        if (allmelt) {
            cout << 0;
            return 0;
        }
    }
    cout << year;
}

 

 

2. 분석

처음에 allmelt에 대한 처리를 하지 않아서 시간초과 판정이 났다. 모두 녹았을 때 0을 출력하는 로직을 따로 만들어줘야한다. 그리고 각 year 마다 주변 0의 개수를 세서 board[x][y]를 그만큼 잠식시키는 것이 이 문제의 독특한 점이다. 그렇게 어렵진 않고 전형적인 BFS 문제이다.

 

3. 시간복잡도

시간복잡도는 O(year * N * M)이다. 최대 n = 300, m = 300, year = 10이므로 year*n*m = 10 * 300 * 300 = 900,000 < 10^8 이므로 시간제한 1초 이내에 통과가 가능하다.