[Algorithm🧬] 백준 10711 : 모래성

문제

성공

모래를 기준으로 돌다가 이미 지나가버렸는데 또 모래가 생기면 어떡하지...? + 시간은 어떻게 측정하지? 라고 생각했는데,
이번 시간에 들어가는 것 (처음에 모래인 것 / 그 다음엔 첫번째 돌았을 때 무너져서 모래가 된 것 / 두번쨰 ...) 만 큐에 넣어서 돌리고, 방금 모래가 된 것을 큐에 다시 넣어주고 다음 시간에 돌리고, 이렇게 하면 되는거였다. for _ in range(len(q)):

import sys
from collections import deque
readl = sys.stdin.readline

# 성이 있는 격자 주변 8방향에 성이 없는 격자의 개수가 성의 강도보다 크거나 같으면 붕괴.

def BFS():
    global castle_cnt

    q = deque()

    # 모래를 기준으로 탐색.
    for i in range(h):
        for j in range(w):
            if sand[i][j] == 0:
                q.append((i, j))

    time = 0

    while q:
        for _ in range(len(q)):
            x, y = q.popleft()

            for dx, dy in ((-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)):
                nx, ny = x + dx, y + dy

                # 가생이 제거
                if not 0 <= nx < h:
                    continue
                if not 0 <= ny < w:
                    continue
                
                # 모래는 신경쓸 필요 없음.
                if sand[nx][ny] == 0:
                    continue

                # 모래 근처에 있는 성이면 -1
                sand[nx][ny] -= 1

                # 만약에 여전히 성이 남아있으면 신경쓸 필요 X
                if sand[nx][ny] != 0:
                    continue

                # 성이 모래가 되는 순간 큐에 넣으면 됨.
                # ch[nx][ny] = ch[x][y] + 1
                # cnt = max(cnt, ch[nx][ny])
                q.append((nx, ny))

        time += 1

    return time - 1


h, w = map(int, readl().split())
sand = [[int(c) if c.isdigit() else 0 for c in readl().rstrip()] for _ in range(h)]

ch = [[0] * w for _ in range(h)]



print(BFS())

TIME LIMT EXCEED

성을 기준으로 돈 코드.
시간 초과 떠서 생각하다보니
모래장을 기준으로 돌고 모래장 하나에 대해서 주변 8개를 -1 하면 되지 않을까? 라는생각이 들었음.

import sys
from collections import deque
readl = sys.stdin.readline

# 성이 있는 격자 주변 8방향에 성이 없는 격자의 개수가 성의 강도보다 크거나 같으면 붕괴.

def BFS():
    global castle_cnt

    q = deque()

    ch = [[0] * w for _ in range(h)]

    # 모래성 다 넣고.
    for i in range(h):
        for j in range(w):
            if sand[i][j] > 0:
                q.append((i, j))


    for i in range(len(q)):
        x, y = q.popleft()

        # 옆이 8면이므로 9인건 무슨짓을 해도 무너질수가 없음.
        if sand[x][y] == 9:
            continue

        if castle_cnt <= 0:
            return castle_cnt

        sand_cnt = 0
        # 주변 8방향에 대해서
        for dx, dy in ((-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)):
            nx, ny = x + dx, y + dy

            if ch[nx][ny] == 1:
                continue

            # 모래 개수 셈.
            if sand[nx][ny] == 0:
                sand_cnt += 1

            # 모래가 성의 강도보다 많으면.
            # 무너짐.
            if sand_cnt >= sand[x][y]:
                castle_cnt -= 1
                sand[x][y] = 0
                break
        

        ch[x][y] = 1

    return castle_cnt



h, w = map(int, readl().split())
sand = [[int(c) if c.isdigit() else 0 for c in readl().rstrip()] for _ in range(h)]


castle_cnt = 0
for i in range(h):
    for j in range(w):
        if sand[i][j] > 0:
            castle_cnt += 1


time = 0
before_cnt = -1
while before_cnt != castle_cnt:
    before_cnt = castle_cnt

    BFS()
    time += 1

    # for i in range(h):
    #     print(sand[i])
    # print()
print(time - 1)