문제에서 제시한 그대로 풀이해보자.
배열의 모든 원소에 대하여 bfs()를 진행하여 반환된 최소 안전 거리의 최댓값을 출력하면 쉽게 답을 구할 수 있다.
그 코드는 아래와 같다.
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().strip().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# 인접 방향(대각선 포함)
d = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]
def bfs(y, x):
q = deque()
q.append((y, x))
visited = [[0] * m for _ in range(n)]
isShark = 0 # flag
while q:
y, x = q.popleft()
for dy, dx in d:
Y = y + dy
X = x + dx
if 0 <= X < m and 0 <= Y < n and visited[Y][X] == 0:
if arr[Y][X] == 0:
q.append((Y, X))
visited[Y][X] = visited[y][x] + 1
else:
ans = visited[y][x] + 1
isShark = 1
if isShark:
break
return ans
ans = 0
for y in range(n):
for x in range(m):
if arr[y][x] != 1:
if ans < bfs(y, x):
ans = bfs(y, x)
print(ans)
정답이지만 아무래도 상어가 있지 않은 모든 원소에 대하여 bfs()를 진행하다보니 시간이 매우 오래걸린다.
역발상을 해보자 (내가 한 것은 아니고 다른 분의 풀이이다)
상어의 위치를 기준으로 한칸씩 이동하면서 이동한 결과를 큐에 넣어가며 풀어보자는 것이다. 다시 말하면 상어들의 위치를 파악 후 큐에 넣은 다음, bfs를 통해 이동거리를 늘려가면 된다.
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
shark = deque()
for i in range(n):
temp = list(map(int, input().split()))
for t in range(m):
if temp[t] == 1:
shark.append((i, t))
arr.append(temp)
mx = [-1, -1, -1, 0, 1, 0, 1, 1]
my = [-1, 0, 1, 1, 1, -1, 0, -1]
def bfs():
while shark:
x, y = shark.popleft()
for k in range(8):
dx = x + mx[k]
dy = y + my[k]
if 0 <= dx < n and 0 <= dy < m:
if arr[dx][dy] == 0:
shark.append((dx, dy))
arr[dx][dy] = arr[x][y] + 1
return
bfs()
safe_dist = 0
for i in range(n):
for j in range(m):
safe_dist = max(safe_dist, arr[i][j])
print(safe_dist - 1)
이렇게 하면 원소별로 bfs() 를 모두 진행할 필요 없이 bfs() 한 번의 실행으로 매우 빠르게 연산이 가능하다.
시간 감소 !