백준 알고리즘 17806번 아기 상어 2(python)

브루트포스 알고리즘 & BFS 문제이다.

from collections import deque
from copy import deepcopy

def bfs(y, x):
    q = deque()
    q.append((y, x))
    a[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < M) and a[Y][X] == -1:
                q.append((Y, X))
                a[Y][X] = a[y][x]+1
                if graph[Y][X] == 1:
                    return a[Y][X]
    return a[y][x]

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
check = [[-1]*M for _ in range(N)]
res = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            a = deepcopy(check)
            res = max(res, bfs(i, j))
print(res)