아기 상어 2

아기 상어 2 - BOJ

import sys
from collections import deque

def bfs(i, j):
    global visited_value
    q = deque()
    dist = 0
    visited_value += 1
    visited[i][j] = visited_value
    q.append([i, j])
    while q:
        dist += 1
        for _ in range(len(q)):
            i, j = q.popleft()
            for a in range(8): # 8방향 각각의 경우에 대해서
                ni, nj = i + di[a], j + dj[a]
                # 방문하지 않은 경우만
                if 0 <= ni < N and 0 <= nj < M and visited[ni][nj] < visited_value:
                    if arr[ni][nj] == 1: # 상어가 존재하면 해당 값 distance return
                        return dist
                    else: # 방문 처리 및 연결된 정보 주입
                        q.append([ni, nj])
                        visited[ni][nj] = visited_value
    return dist - 1

N, M = map(int, input().split())
arr = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
di = [0, 0, -1, 1, -1, -1, 1, 1]
dj = [-1, 1, 0, 0, -1, 1, -1, 1]
visited_value = 0
max_dist = 0

for i in range(N):
    for j in range(M):
        if arr[i][j] == 0: # 상어가 없는 node부터 시작해서
            max_dist = max(max_dist, bfs(i, j)) # 최대값 갱신

print(max_dist)