1091.Shortest Path in Binary Matrix

My code

시간 복잡도 탈락. 이유는 탐색 시 queue에서 같은 거리 내의 블록을 한번에 꺼내지 않고 하나씩 꺼내어 봤기 때문

from typing import List
from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] != 0 or grid[-1][-1] != 0:
            return -1

        
        queue = deque()
        queue.append(((0,0),1))
        dx = [-1, 0, 1, -1, 1, -1, 0, 1]
        dy = [-1, -1, -1, 0, 0, 1, 1, 1]
        n = len(grid)
        visited = {(0,0)}

        while queue:
            (cur_x,cur_y),dist = queue.popleft()
            if cur_x == n-1 and cur_y == n-1:
                 return dist
            
            for i in range(8):
                next_x = cur_x + dx[i]
                next_y = cur_y + dy[i]

                if next_x in range(n) and next_y in range(n) and grid[next_y][next_x] == 0 and (next_y,next_x) not in visited:
                    queue.append(((next_x,next_y),dist + 1))
                    visited.add((next_x,next_y))

Answer

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # check if source and target are not clear cells
        if grid[0][0] != 0 or grid[-1][-1] != 0:
            return -1
        
        N = len(grid)            
        # offsets required for all 8 directions
        offsets = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        
        q = deque()
        q.append((0,0)) # starting point
        visited = {(0, 0)}
        
        
        # finds unvisited clear cells using 8 offsets
        def get_neighbours(x,y):
            for x_offset, y_offset in offsets:
                new_row = x + x_offset
                new_col = y + y_offset
                
                if 0 <= new_row < N and 0 <= new_col < N and not grid[new_row][new_col] and (new_row, new_col) not in visited:
                    yield (new_row, new_col)                                                
            
        
        current_distance = 1 # start with one clear cell
        # standard iterative BFS traversal
        while q:
            length = len(q)
            
            # loop through all the cells at the same distance
            for _ in range(length):
                row, col = q.popleft()
                
                if row == N-1 and col==N-1: # reached target
                    return current_distance
                
                # loop though all valid neignbours
                for p in get_neighbours(row, col):
                    visited.add(p)
                    q.append(p)
                                    
            current_distance+=1 # update the level or distance from source
        
        return -1