이번 문제는 BFS를 통해 해결하였다. 처음에는 단순하게 좌표들을 돌며 모래성이 있는 좌표를 큐에 담고, BFS를 통해 큐를 탐색하며 8개의 좌표를 확인하며 모래성이 없는 좌표의 갯수를 세어 모래성의 사라짐 유무를 판단하도록 하였다. 만약 모래성이 사라지지 않는다면 새로운 큐에 좌표를 넣도록 하였다. 이렇게 작성된 bfs()함수는 while문을 통해 여러번 실행되도록 하였다. 그러나 이 방법은 시간초과가 발생하였다.

그래서 새로운 방법에 대해 생각하다가, 다른 사람의 풀이를 참고하게 되었다. 새로운 관점으로 모래성이 없는 좌표를 큐에 담고, 이 좌표들을 돌며 모래성을 만나면 1씩 감소시키는 방법이었다. 처음에는 이 방법이 왜 논리적으로 맞는지 이해가 안가 생각해보게 되었다. 이 문제에서 중요한 것은 모래성의 단단함 보다는 모래성의 유무와 모래성에 영향을 미치는 좌표의 갯수가 중요하기 때문에 가능한 방법이었다. 방문처리 리스트에는 시간에 해당하는 수를 넣어 최종 상태가 되기까지 얼마나 시간이 걸리는지 체크하는데 사용되었다.

Code

처음 제출 코드 (시간초과)

import copy
from collections import deque
h, w = map(int, input().split())
grid = [list(str(input())) for _ in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] != '.':
            q.append((i, j))
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1], [0, 1, 1, 1, 0, -1, -1, -1]
def bfs():
    global q, grid
    new_q = deque()
    new_grid = [['.' for _ in range(w)] for _ in range(h)]
    while q:
        y, x = q.popleft()
        cnt = 0
        for i in range(8):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if grid[ny][nx] == '.':
                    cnt += 1
        if cnt < int(grid[y][x]):
            new_grid[y][x] = grid[y][x]
            new_q.append((y, x))
    q = copy.deepcopy(new_q)
    if grid == new_grid:
        return False
    else:
        grid = copy.deepcopy(new_grid)
        return True
answer = 0
while True:
    if not bfs():
        break
    answer += 1
print(answer)

정답 코드

from collections import deque
h, w = map(int, input().split())
grid = [list(str(input())) for _ in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == '.':
            q.append((i, j))
dy, dx = [-1, -1, 0, 1, 1, 1, 0, -1], [0, 1, 1, 1, 0, -1, -1, -1]
answer = 0
def bfs():
    result = 0
    visited = [[0 for _ in range(w)] for _ in range(h)]
    while q:
        y, x = q.popleft()
        for i in range(8):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if grid[ny][nx] != '.':
                    grid[ny][nx] = str(int(grid[ny][nx])-1)
                    if grid[ny][nx] == '0':
                        grid[ny][nx] = '.'
                        q.append((ny, nx))
                        visited[ny][nx] = visited[y][x]+1
                        result = max(result, visited[ny][nx])
    return result
print(bfs())