[알고리즘 문제] 백준2537 - 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

bfs와 dfs를 활용하여 문제를 풀었습니다. 먼저 각각 빙산의 높이를 인접한 바다의 수만큼 감소시키고(bfs),  빙산을 2덩어리 이상으로 분리할 수 있는지 체크합니다. 여기서 분리할 수 있으면 그때의 시간을 출력하고, que에서 빙산이 없으면 0을 출력하게 합니다.

 

처음 배열의 크기를 10000 x 10000을 했더니 메모리 초과가 나와서 문제에서 사용한 모든 배열을 동적할당을 하였습니다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

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

struct Info
{
    int x;
    int y;
    int height;
};

int **arr;
int **visited;

void dfs(int y, int x, int h) // 연결되어 있는 빙산을 같은 숫자로 연결
{
    for (int i = 0; i < 4; i++)
    {
        int newY = y + dy[i];
        int newX = x + dx[i];

        if (arr[newY][newX] && !visited[newY][newX])
        {
            visited[newY][newX] = h;
            dfs(newY, newX, h);
        }
    }
}
int divide() // 몇개의 덩어리로 분리되는지
{
    visited = new int *[height + 1];
    for (int i = 0; i < height + 1; ++i)
    {
        visited[i] = new int[width + 1];
        memset(visited[i], 0, sizeof(int) * width + 1);
    }
    int h = 0; // 연결된 덩어리에 1,2,3...번호를 붙임

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (arr[y][x] && !visited[y][x])
            {
                h++;
                visited[y][x] = h;
                dfs(y, x, h);
            }
        }
    }

    return h;
}

int main()
{
    cin >> height >> width;
    queue<pair<int, int>> que;

    arr = new int *[height + 1];
    for (int i = 0; i < height + 1; ++i)
    {
        arr[i] = new int[width + 1];
        memset(arr[i], 0, sizeof(int) * width + 1);
    }

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            cin >> arr[y][x];
            if (arr[y][x])
            {
                que.push({y, x});
            }
        }
    }

    int ans = 1;
    while (!que.empty())
    {
        int size = que.size();
        vector<Info> vec;

        for (int k = 0; k < size; k++) // que에 있는 모든 빙산의 높이를 수정함 -> 1년이 지남
        {
            int y = que.front().first;
            int x = que.front().second;
            que.pop();
            int h = arr[y][x];

            for (int i = 0; i < 4; i++)
            {
                int newY = y + dy[i];
                int newX = x + dx[i];

                if (arr[newY][newX] == 0 && h) // 인접한 바다가 있고 빙산의 높이가 0보다 크다면 높이 감소
                {
                    h--;
                }
            }

            vec.push_back({x, y, h});
            if (h)
            {
                que.push({y, x}); // 빙산의 높이가 0보다 크다면 que에 다시 넣음
            }
        }

        for (int i = 0; i < vec.size(); i++)
        {
            arr[vec[i].y][vec[i].x] = vec[i].height; // 각각의 빙산높이는 독립적으로 계산되어야 함
        }

        int count = divide();
        if (count >= 2) // 분할된 덩어리가 2개 이상이면 현재 높이를 시간을 출력
        {
            cout << ans << endl;
            return 0;
        }
        ans++;
    }

    cout << 0 << endl;
    return 0;
}