[백준] 17086번 - 아기 상어 2

📩 출처

문제

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

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

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

입력

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

출력

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

👉 생각

• 이차원 배열이 0인 곳을 너비우선 탐색을 한다.
• 0인 좌표에서 1을 가장 빨리 찾을 때의 좌표를 반환하고, 모든 0인 좌표의 값을 비교해서 가장 큰 값을 출력한다.

from collections import deque
import sys

def bfs(x,y):
    q = deque([])
    q.append((x, y, 0))
    visited = [[0] * m for _ in range(n)]
    visited[x][y] = 1
    while q:
        x, y, cnt = q.popleft()
        if arr[x][y]:
            return cnt

        for dx, dy in [(-1,0),(-1,1),(-1,-1),(0,-1),(0,1),(1,0),(1,-1),(1,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                q.append((nx, ny, cnt + 1))
                visited[nx][ny] = 1

n, m = map(int, input().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

res = 0
for i in range(n):
    for j in range(m):
        res = max(res, bfs(i,j))

print(res)