[BOJ 백준] 10711번 : 모래성(Python, 파이썬)

www.acmicpc.net/problem/10711

10711번: 모래성

맨 처음에는 단순히 전체 배열을 탐색하는 BFS 코드를 짰더니 시간 초과가 발생했다.

최악의 경우 O(N^3) 까지 들어 올 수 있기 때문에 그렇다.

 

 

그래서 조금 다른 방법을 사용했다.

• 비어있는 부분의 위치를 모두 큐에 삽입하고, 이를 기준으로 BFS 탐색을 한다.
• 8방 탐색을 하는 동안 모래성을 만나면 해당 모래성에서 1을 빼주고, 큐에서 popleft를 한다.
• 만약 모래성의 값이 0이 되면 해당 좌표를 큐에 삽입해준다.
• 큐가 비게 되면 반복문을 종료한다.

 

이 때 조금 헷갈리는 것이, 문제에서는 분명

 

자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다.

 

라고 되어있기 때문에 모래성에서 1을 빼면 안되지 않나 라고 생각할 수 있다.

 

하지만, 모래성이 파도에 의해 무너지는 것은 모래성의 값이 0이 될 때만 이다.

예를들어, 모래성의 튼튼함이 6이고 해당 위치에서 8개 방향 중 모래가 없는 부분이 5라면 이 모래성은 무너지지 않는다.

 

즉, 튼튼함이 6에서 5를 뺀 1이 되어도 이전 상황(튼튼함이 6)과 다를게 없다는 것이다.

 

또한, 이때 -1을 해준 모래가 없는 부분의 좌표는 이미 큐에서 빠진 상황이므로 파도가 쳐서 깎여진 모래성은 반복문이 다시 돌 때 다시 깎이지 않는다. 

 

 

소스코드

 

import sys
from collections import deque

H, W = map(int, input().split())
Dir = [(-1,0), (1,0), (0,-1), (0,1), (1,-1), (1,1), (-1,-1), (-1,1)]
board = [list(input()) for _ in range(H)]
visited = [[0 for i in range(W)] for j in range(H)]
dq = deque()
for i in range(H): # 빈 곳은 0으로, 나머지는 int로 전환
    for j in range(W):
        if board[i][j] == '.':
            board[i][j] = 0 
            dq.append((i, j))
        else:
            board[i][j] = int(board[i][j])    
answer = 0

while len(dq):    
    y, x = dq.popleft()
    for k in range(len(Dir)):
        ny = y + Dir[k][0]
        nx = x + Dir[k][1]
        if 0 > ny or ny >= H or 0 > nx or nx >= W:
            continue
        if board[ny][nx] != 0:
            board[ny][nx] -= 1
            if board[ny][nx] == 0:
                visited[ny][nx] = visited[y][x] + 1 # 몇번 파도가 쳤는지 기록
                answer = max(answer, visited[ny][nx])
                dq.append((ny, nx))

print(answer)