BJ 2573 //빙산

 

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

 

 

• 문제 배경:
  • 지구 온난화로 인해 북극의 빙산이 녹고 있다.
  • 2차원 배열에서 빙산의 높이 정보를 각 칸에 제공하며, 빙산이 없는 바다는 0으로 표시된다.
  • 빙산은 동서남북으로 인접한 바다의 개수만큼 높이가 줄어든다.
  • 빙산의 높이가 0이 되면 해당 칸은 바다가 된다.
• 목표:
  • 빙산이 최소 두 덩어리로 나뉘는 시간을 구하라.
  • 만약 빙산이 끝까지 녹아도 분리되지 않는다면 0을 출력한다.
• 입력:
  • 첫 번째 줄: 2차원 배열의 행과 열의 개수 N과 M (3≤N,M≤3003).
  • 이후 NNN개의 줄: 2차원 배열의 빙산 높이 정보. 바다는 0이며, 빙산의 높이는 10 이하의 정수.
• 출력:
  • 빙산이 두 덩어리 이상으로 분리되는 최소 시간을 출력.
  • 빙산이 끝까지 녹아도 분리되지 않으면 0을 출력.
• 제약:
  • N×M≤10,000N \times M \leq 10,000N×M≤10,000, 즉 배열 크기가 최대 10,000임.
  • 빙산이 모두 녹는 과정을 정확히 시뮬레이션해야 한다.

 

 

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

int n, m;
vector<vector<int>> iceberg;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };


void bfs(int x, int y, vector<vector<bool>>& visited)
{
    queue<pair<int, int>> q;
    q.push({ x, y });
    visited[x][y] = true;

    while (!q.empty()) {
        int cx = q.front().first, cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i], ny = cy + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && iceberg[nx][ny] > 0 && !visited[nx][ny])
            {
                visited[nx][ny] = true;
                q.push({ nx, ny });
            }
        }
    }
}

// 빙산 녹이기
void meltIceberg() {
    vector<vector<int>> temp = iceberg;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (iceberg[i][j] > 0)
            {
                int seaCount = 0;
                for (int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k], ny = j + dy[k];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && iceberg[nx][ny] == 0) seaCount++;
                }
                temp[i][j] = max(0, iceberg[i][j] - seaCount);
            }
        }
    }
    iceberg = temp;
}

// 빙산 덩어리 개수 세기
int countChunks()
{
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int chunks = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (iceberg[i][j] > 0 && !visited[i][j])
            {
                bfs(i, j, visited);
                chunks++;
            }
        }
    }
    return chunks;
}

int main()
{
    cin >> n >> m;
    iceberg.resize(n, vector<int>(m));

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

    int time = 0;
    while (true)
    {
        int chunks = countChunks();
        if (chunks >= 2)
        { // 두 덩어리로 분리
            cout << time << "\n";
            break;
        }
        if (chunks == 0)
        { // 빙산이 모두 녹음
            cout << 0 << "\n";
            break;
        }
        meltIceberg();
        time++;
    }

    return 0;
}