BOJ 17086번 - 아기 상어 2

[백준 온라인 저지 링크]

17086번: 아기 상어 2

 

[정답 코드 - Python]

from collections import deque
N, M = map(int, input().split())
max_cnt = 0
queue = deque()
board = []

dy = [-1, -1, 0, 1, 1, 1, 0, -1]
dx = [0, 1, 1, 1, 0, -1, -1, -1]

for i in range(N):
    board.append(list(map(int, input().split())))


def BFS(q):
    while q:
        y, x = q.popleft()
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < M:
                // 다음 칸이 0이 아니라면, 이미 다른 상어(출발점)에서 밟은 공간이라는 의미입니다.
                if board[ny][nx] == 0:
                    board[ny][nx] = board[y][x] + 1
                    q.append((ny, nx))


for row in range(N):
    for col in range(M):
        if board[row][col] == 1:
            queue.append((row, col))


// 상어가 있는 지점을 큐에 한번에 집어넣습니다.
// 이러면 각 상어가 있는 지점들로부터 1씩 뻗어나가게 되어, 따로 방문 여부 처리를 해주지 않아도 됩니다!
BFS(queue)

// 최대 거리 계산
for row in range(N):
    for col in range(M):
        if board[row][col] >= max_cnt:
            max_cnt = board[row][col]

print(max_cnt - 1)