아기 상어 2

백준 17086

안전 거리의 최댓값 구하기.

• N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.
• 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.
• 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다.

입출력

입력	출력
5 4 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1	2
7 4 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	2

---

접근 방식

: bfs사용. 모든 1에서 탐색 어떻게?

알게된 점

전에 풀어본 백준 토마토 문제와 같다.
입력 받은 공간의 상태 값이 1인 좌표를 큐에 넣고 bfs진행.
visited의 max값 출력.

코드

from collections import deque

def bfs():
    
    dx = [-1,1,0,0,-1,-1,1,1]
    dy = [0,0,-1,1,-1,1,-1,1]

    while q:
        x, y = q.popleft()
        for k in range(8):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0<=nx<n and 0<=ny<m:
                if maps[nx][ny] == 0 and visited[nx][ny]==0::
                    visited[nx][ny] = visited[x][y]+1
                    q.append((nx, ny))


n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

q = deque()
for i in range(n):
    for j in range(m):
        if maps[i][j] == 1:
            q.append((i, j))
bfs()
print(max(map(max, visited)))