백준 17086 아기 상어 2 python

문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력
첫째 줄에 안전 거리의 최댓값을 출력한다.

풀이

from collections import deque

n, m = map(int, input().split())

maps = [list(map(int, input().split())) for _ in range(n)]
# 영역의 크기와 아기 상어가 있는 영역을 확인해줍니다.

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
# 8방향 이동을 설정해줍니다.

q = deque()
for i in range(n):
    for j in range(m):
        if maps[i][j]:
            q.append((i, j))
# 아기상어가 있는 위치를 q에 받아줍니다.

longest = 0
while q:
    x, y = q.popleft()
    for i in range(8):
        nx = dx[i] + x
        ny = dy[i] + y
        if nx in range(n) and ny in range(m):
            if not maps[nx][ny]:
                maps[nx][ny] = maps[x][y] + 1
                longest = maps[nx][ny]
                q.append((nx, ny))
                # 큐의 값을 빼내면서 확인하여 8방향 이동이 가능한지 확인하고 상어로부터
                # 얼마나 떨어져있는지 값을 저장하여줍니다.

print(longest - 1)
# 상어가 있는 1부터 값을 더하여주었으므로 마지막에 저장된 값에 1을 뺀 값을 출력해줍니다.