문제

10711번: 모래성

풀이

처음엔 완전탐색으로 해결해보려 했다. 파도가 칠때마다 모든 모래성의 튼튼함 정도와 주변 모래성의 개수를 확인해서 해당 모래성이 무너질지 아닐지를 판단했는데, 당연하게도 시간초과가 발생했다.

좀 더 빠른 방법을 위해 파도가 칠때마다 모든 모래성을 판단하는것이 아닌, 파도가 쳤을 때 무너진 모래성 주변만을 탐색해서 판단하기로 했다.

모래성이 없는 위치를 전부 큐에 넣고 bfs로 탐색하며 해당 위치에 영향을 맏는 모래성의 튼튼함 정도를 1씩 깎았다. 모래성의 튼튼함 정도가 0이 될 경우 buffer에 임시로 저장해두고 다음 파도가 칠때 다른 bfs 탐색을 시작하기 전에 큐에 buffer에 있던 위치들을 넣는다. 이미 무너져서 튼튼함 정도가 0인 모래성들과의 중복을 피할 수 있도록 주의한다.
buffer의 크기가 0이 될 때까지 반복하여 몇번의 bfs 탐색을 했는지 출력한다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int w, h;
vector<vector<int>> sandCastle;
vector<pair<int, int>> buffer;
vector<pair<int, int>> dir { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };
int cnt = 0;

bool OOB(int x, int y)
{
    return x < 0 || x >= h || y < 0 || y >= w;
}

void bfs()
{
    queue<pair<int, int>> q;
    for (auto i : buffer)
        q.push(i);

    buffer.clear();

    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (auto d : dir)
        {
            int nx = d.first + x;
            int ny = d.second + y;

            if (OOB(nx, ny))
                continue;

            --sandCastle[nx][ny];
            if (sandCastle[nx][ny] == 0)
                buffer.push_back({nx, ny});

        }
    }
}

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

    cin >> h >> w;
    sandCastle.resize(h);
    for (int i=0; i<h; ++i)
    {
        sandCastle[i].reserve(w);
        string input;
        cin >> input;
        for (auto c : input)
        {
            if (c == '.')
                sandCastle[i].push_back(0);
            else
                sandCastle[i].push_back(c - '0');
        }
    }

    for (int i=0; i < h; ++i)
    {
        for (int j=0; j <w; ++j)
        {
            if (sandCastle[i][j] == 0)
                buffer.push_back({i, j});
        }
    }

    while (true)
    {
        bfs();
        if (buffer.size() == 0)
            break;
        ++cnt;
    }
    
    cout << cnt << endl;

    return 0;
}