[BOJ/백준] 10711 모래성

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
N,M = map(int,input().split())
 
 
arr = [list(input()) for _ in range(N)]
 
sand_deque = deque()
 
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
for x in range(N):
    for y in range(M):
        if not arr[x][y].isdigit():
            sand_deque.append((x,y))
        else:
            arr[x][y] = int(arr[x][y])
 
 
 
time = 0
 
while True:
    remove_sand = deque()
 
    while sand_deque:
        x,y = sand_deque.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0<=nx<N and 0<=ny<M):continue
            if arr[nx][ny] != '.':
                arr[nx][ny] -= 1
                if arr[nx][ny] == 0:
                    remove_sand.append((nx,ny))
                    arr[nx][ny] = '.'
    if remove_sand:
        sand_deque.extend(remove_sand)
        time += 1
    else:
        break
 
print(time)

 

 

처음에 dict을 이용해서 날먹할려다가 시간초과가 났던 문제이다.

 

문제를 푸는 방식은 다음과 같다. 모든 모래들은 하나의 큐에 넣은 뒤에, 8방향의 모래가 아닌곳의 개수를 -1씩 해준다.

 

그러면서 0이 되면, remove_sand라는 큐에 넣어준다.

 

그러면 이 모래성이 더이상 무너지지 않는 경우는 remove_sand가 비어있을때이다.

 

그래서 remove_sand가 비어있으면 break를 해주고, 있을때에는 sand_deque에 extend 해주고 그 때 time을 1 늘려준다.

 

 

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
def bfs(queue):
    dx = [-1,0,1,-1,1,-1,0,1]
    dy = [-1,-1,-1,0,0,1,1,1]
    while queue:
        x,y,cnt = queue.popleft()
 
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if not(0<=nx<N and 0<=ny<M):continue
            if arr[nx][ny]:
                arr[nx][ny] -= 1
                if not arr[nx][ny]:
                    queue.append((nx,ny,cnt+1))
 
    return cnt
 
N,M = map(int,input().split())
 
 
arr = [list(input()) for _ in range(N)]
 
 
sand_deque = deque()
for x in range(N):
    for y in range(M):
        if arr[x][y].isdigit():
            arr[x][y] = int(arr[x][y])
        else:
            arr[x][y] = 0
            sand_deque.append((x,y,0))
 
 
 
print(bfs(sand_deque))

 이 코드는 좀 더 깔끔한 방식으로 코드를 바꾼 방식이다.

 

원리 자체는 똑같다.