[BOJ] 백준 10711 모래성

출처: https://www.acmicpc.net/problem/10711

 Input 

10 10

..........

.99999999.

.9.323239.

.91444449.

.91444449.

.91444449.

.91444449.

.91232329.

.99999999.

..........

 

 Output 

35

 

① 처음 input으로 주어지는 파도의 위치(x, y)와 경과 시간(cost)를 큐에 저장합니다.

② Queue에 값을 한 개씩 꺼내어 인접한 모래성의 강도를 낮춥니다.

    다른 파도가 존재하는 곳이거나 모래성의 강도가 9인 경우는 continue

    (파도가 8면에 존재할 수 있으므로 모래성의 강도 = 9 인 경우 무너지지 않습니다.)

③ 무너지는 모래성이 존재한다면 다음 차례에 파도가 되므로 Queue에 저장합니다.

---

#include <stdio.h>
const int MAX_HW = 1000 + 5;
const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
const int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
struct Node {
    int x, y, cost;
}que[MAX_HW * MAX_HW * 8];
int H, W, ans;
char map[MAX_HW][MAX_HW];
int fr, re;
 
void BFS() {
    Node cur;
    while (fr < re) {
        cur = que[fr++];
        for (int i = 0; i < 8; ++i) {
            int nX = cur.x + dx[i];
            int nY = cur.y + dy[i];
            if (nX < 0 || nY < 0 || nX >= H || nY >= W)
                continue;
            if (map[nX][nY] == '.' || map[nX][nY] == '9')
                continue;
            if (--map[nX][nY] == '0') {
                que[re++] = { nX, nY, cur.cost + 1 };
                ans = ans < cur.cost + 1 ? cur.cost + 1 : ans;
            }
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &H, &W);
    for (int i = 0; i < H; ++i) {
        scanf("%s", map[i]);
        for (int j = 0; j < W; ++j) {
            if (map[i][j] == '.') {
                que[re++] = { i, j, 0 };
            }
        }
    }
    BFS();
    printf("%d\n", ans);
}