문제 풀이
상어에서부터 안전 거리를 계산해야 하므로 값이 1인 좌표를 큐에 넣고 bfs로 탐색한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
# 대각선 방향 포함한 8개 방향
dx = [-1, -1, -1, 0, 1, 0, 1, 1]
dy = [-1, 0, 1, 1, 1, -1, 0, -1]
q = deque()
for row in range(n):
tmp = list(map(int, input().split()))
for col in range(m):
if tmp[col] == 1:
# 상어에서부터 거리를 계산해야 하므로 큐에 넣기
q.append((row, col))
arr.append(tmp)
def bfs():
while q:
x, y = q.popleft()
for direction in range(len(dx)):
nx, ny = x + dx[direction], y + dy[direction]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if arr[nx][ny] == 0:
q.append((nx, ny))
arr[nx][ny] = arr[x][y] + 1
bfs()
dist = 0
for row in range(n):
for col in range(m):
dist = max(arr[row][col], dist)
print(dist - 1) # 거리에서 자기 자신 빼주기