[백준 19711번] 파이썬 - 모래성

백준 10711 - 모래성

시간 제한 1초, 메모리 제한 256MB

# 조건

• 명우가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다.
• 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다.
• 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다.
  • 그 이외의 경우는 파도가 쳐도 무너지지 않는다.
  • 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다.
• 이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다.
• 모래성을 완성한 명우는 문득 자신이 만든 예술품의 수명이 궁금해졌다.
• 모래성은 위에 서술한 바와 같이 파도가 한번 칠 때마다 특정 부분이 무너저내리는 방식으로 모양이 변화된다.
• 모래성이 더이상 모양이 변하지 않게 되려면 (모양이 수렴되려면) 파도가 몇번 쳐야하는지 구해보자.

입력

• 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000)
• 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다.
• 각 문자는 19 사이의 숫자, 또는 '.' 이다. 19는 그 격자의 모래의 강도를 나타내며, '.'는 모래가 없다는 뜻이다.
• 모래성은 격자의 가장자리와 접해 있지 않다.

출력

• 몇 번의 파도가 몰려오고나서야 모래성의 상태가 수렴하는지를 구한다.

# 접근 방법

• 구현 문제라고 생각하고 주어진 조건 대로 파도로 인해 모래성이 변하지 않을 때까지 모든 격자를 탐색하면 시간 초과가 발생한다.
• 따라서, 탐색의 시간을 줄이기 위하여 아래와 같이 풀었다.
  • 현재 비어있는 곳을 queue에 담아준다.
  • 해당 q에서 좌표를 뽑은 후, 8방을 탐색하며 모래가 존재한다면 -1씩 해준다.
  • -1을 한 후 해당 모래성이 무너졌다면 temp 에 담아준 후 원래 q가 비었다면 파도 +1을 해준 후 temp를 옮겨 담아 준다.
• 또는 count 배열을 선언해주고, 0이 될 때마다 현재 값 +1을 해준 후 result를 더 큰 값으로 갱신해주는 방법도 있다.

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

def solve():
    H, W = map(int, input().split())
    sands = [list(input().strip()) for _ in range(H)]
    empty = deque()

    # 상하좌우 좌상 우상 좌하 우하
    di, dj = [-1, 1, 0, 0, -1, -1, 1, 1], [0, 0, -1, 1, -1, 1, -1, 1]


    for i in range(H):
        for j in range(W):
            if sands[i][j] == '.':
                empty.append((i, j))
            else:    
                sands[i][j] = int(sands[i][j])

    flag = True
    result = 0

    while flag:
        result += 1
        flag = False
        temp = deque()
        while empty:
            si, sj = empty.popleft()
            for d in range(8):
                ni, nj = si+di[d], sj+dj[d]
                if 0<=ni<H and 0<=nj<W and sands[ni][nj] != '.':
                    sands[ni][nj] -= 1
                    if sands[ni][nj] == 0:
                        sands[ni][nj] = '.'
                        temp.append((ni, nj))
                        flag = True

        if flag:
            empty = temp


    print(result-1)

if __name__ == "__main__":
    solve()