모래성 10711

문제

접근 방법

BFS이다.
순서를 나타내자면 이렇다.

1. 모래가 없는 부분 저장.
2. 저장된 값 주변 탐색 중의 만약 모래가 존재한다면 감소 시켜줌 (모래가 없어진다면 해당 위치 저장해 둠)
3. 모래가 없어진 부분이 존재한다면 파도의 개수 갱신시켜 주고 2로 돌아감.
4. 출력해 줌

모래가 없는 부분에서 시작하여서 주변에 다른 후보를 탐색하고 해당 후보에서 다시 주변을 탐색하기에 BFS라고 볼 수 있다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pos;
string line;
int H, W, dy[] = {0, 0, 1, -1, 1, 1, -1, -1}, dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
vector<vector<int>> map;
queue<pos> target, buffer;
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> H >> W;
    map = vector<vector<int>>(H, vector<int>(W));
    for (int i = 0; i < H; ++i)
    {
        cin >> line;
        for (int j = 0; j < W; ++j)
            if (line[j] == '.')
            {
                map[i][j] = 0;
                target.push({i, j});
            }
            else
                map[i][j] = line[j] - '0';
    }
}
bool isOut(int y, int x)
{
    return y < 0 || x < 0 || y >= H || x >= W;
}
int solve()
{
    int ret = 0;
    while (true)
    {
        while (!target.empty())
        {
            pos cur = target.front();
            target.pop();
            for (int i = 0; i < 8; ++i)
            {
                int ny = cur.first + dy[i], nx = cur.second + dx[i];
                if (isOut(ny, nx) || !map[ny][nx])
                    continue;
                if (--map[ny][nx] == 0)
                    buffer.push({ny, nx});
            }
        }
        if (buffer.empty())
            return ret;
        buffer.swap(target);
        ++ret;
    }
}
int main()
{
    input();
    cout << solve();
    return 0;
}

풀이

오랜만의 꽤 높은 등수를 얻은 것 같다.

힌트를 보면 마치 조건을 충족해야 휩쓸리는 것처럼 보인다.
그렇기에 나는 조건 충족하는 것들 저장, 중복되지 않게 확인 등의 작업을 해줬고 그 결과 시간 초과가 났다. (지도를 수정하지 않기에 해당 위치가 파도에 휩쓸리는지 확인하기 위해 또 8방향을 확인해야 했다)

힌트가 오히려 독이 된 케이스이다.
물론 이해를 돕기 위한 힌트이지만 고정 관념이 생긴 느낌이 들었다.
(함정이라고 볼 수 있다고 생각한다)

중복 확인을 위해 배열을 초기화하면 배열의 크기가 커서 시간 초과가 난다. 1000^4가 될 수 있기 때문이다. (배열의 크기만큼 탐색할 수 있기 때문이다. 예제 입력 2와 비슷한 방식으로 길게 나올 수 있기 때문)

그러한 점이 바로 생각이 안 나서 시간 초과를 해결 못 했었다.

파도로 벽을 감소시켜도 된다는 점을 알게 되고 풀 수 있게 됐다.