백준 17086 아기상어2
from collections import deque
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, -1, -1, 1, 1]
check = [[-1] * m for _ in range(n)]
sharklist = []
for i in range(n):
for j in range(m):
if g[i][j] == 1:
sharklist.append((i, j))
q = deque()
for i in range(len(sharklist)):
x, y = sharklist[i]
q.append((x, y))
check[x][y] = 0
while q:
x, y = q.popleft()
for i in range(8):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if check[nx][ny] == -1 and g[nx][ny] == 0:
check[nx][ny] = check[x][y] + 1
q.append((nx, ny))
print(max(max(check)))
상어를 모두 큐에 넣고 상어로부터 빈칸의 최소거리를 구하는 방식이 안되는 이유?
시간복잡도 계산
Author And Source
이 문제에 관하여(백준 17086 아기상어2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gmlwlswldbs/백준-17086-아기상어2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)