[백준] 17086번 아기 상어 2

💡문제접근

BFS(상하좌우 + 대각선) 유형 너비 우선 탐색

💡코드(메모리 : 34192KB, 시간 : 68ms)

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
queue = deque()

def BFS():
    while queue:
        y, x = queue.popleft()

        dy = [0, 1, 1, 1, 0, -1, -1, -1]
        dx = [-1, -1, 0, 1, 1, 1, 0, -1]
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            if 0 <= ny < N and 0 <= nx < M:
                if not graph[ny][nx]:
                    graph[ny][nx] = graph[y][x] + 1
                    queue.append([ny, nx])

distance = 0
# 상어의 위치를 기준으로 해당 칸의 안전 거리를 계산
for y in range(N):
    for x in range(M):
        if graph[y][x] == 1:
            queue.append([y, x])

BFS()
# 안전 거리가 가장 큰 칸을 구하기
for i in range(N):
    temp = max(graph[i])
    distance = max(distance, temp)
print(distance-1)

💡소요시간 : 27m