빙산 2573

문제

접근 방법

그래프 탐색 문제를 많이 풀어봤다면 알겠지만 그래프 탐색으로 영역이 나눠지는지 확인하는 문제이다.
하지만 한 가지 문제가 있다.
녹는 것에 대한 처리를 그대로 적용하면 안 된다는 것이다.
시간에 따라 다 같이 녹아야 하는데 앞에서부터 처리해줄 시 이미 물이 되어버린 빙하가 다음 빙하에 영향을 미치기 때문이다.
그렇기에 따로 배열을 만들어 가중치를 저장해두면 해결할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> map, melt;
int dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1};
int N, M;
int melting()
{
    int ice = 0;
    fill(melt.begin(), melt.end(), vector<int>(M));
    // melt = vector<vector<int>>(N, vector<int>(M)); // 얼마나 녹은지 확인
    for (int i = 1; i < N - 1; ++i)
        for (int j = 1; j < M - 1; ++j)
            if (map[i][j])
            {
                ++ice;
                for (int k = 0; k < 4; ++k)
                {
                    int y = i + dy[k], x = j + dx[k];
                    if (!map[y][x])
                        ++melt[i][j];
                }
            }
    for (int i = 1; i < N - 1; ++i)
        for (int j = 1; j < M - 1; ++j)
        {
            map[i][j] -= melt[i][j];
            if (map[i][j] < 0)
                map[i][j] = 0;
        }
    return ice;
}
bool isPart()
{
    fill(melt.begin(), melt.end(), vector<int>(M)); // visted로 재활용
    bool once = false;
    for (int i = 1; i < N - 1; ++i)
        for (int j = 1; j < M - 1; ++j)
        {
            if (melt[i][j] || !map[i][j])
                continue;
            if (once)
                return once;
            once = true;
            queue<pair<int, int>> bfs;
            bfs.push({i, j});
            melt[i][j] = true;
            while (!bfs.empty())
            {
                pair<int, int> cur = bfs.front();
                bfs.pop();
                for (int k = 0; k < 4; ++k)
                {
                    int y = cur.first + dy[k], x = cur.second + dx[k];
                    if (!melt[y][x] && map[y][x])
                    {
                        melt[y][x] = true;
                        bfs.push({y, x});
                    }
                }
            }
        }
    return false;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    map = melt = vector<vector<int>>(N, vector<int>(M));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
        {
            cin >> map[i][j];
        }
    int day = 1;
    while (true)
    {
        int ice = melting();
        if (!ice)
        {
            cout << 0;
            break;
        }
        if (isPart())
        {
            cout << day;
            break;
        }
        else
            ++day;
    }
    return 0;
}

풀이

BFS, DFS를 통해 영역의 개수를 확인,
한 번에 처리하기 위해 저장해두는 법 이 두 가지를 생각해내면 풀 수 있다.
생성자로 초기화하는 방식을 사용했더니 시간이 꽤 많이 나왔다. fill을 이용하여 초기화했더니 4분의 3정도로 줄어들었다. 눈에 띄게 줄어든 것을 보니 여태까지 잘못된 방식으로 초기화했구나 싶었다.