Graphs: 1091. Shortest Path in Binary Matrix

1091. Shortest Path in Binary Matrix

 

가장 짧은 경로 문제: BFS => 큐     cf) 목적지까지 갈수있는 경로 개수: DFS => 재귀 

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        N = len(grid) # n x n matrix

        if not grid:
            return -1
        if grid[0][0] == 1 or grid[N-1][N-1] == 1:
            return -1

        # shotedpath: using bfs, que
        def bfs(grid):
            q = deque()
            visit = set()

            q.append((0, 0)) # top left
            visit.add((0, 0))
            legnth = 1 # 초기 길이, 시작점 포함

            while q:                
                for _ in range(len(q)):
                    r, c = q.popleft()

                    if r == N-1 and c == N-1: # bottom-right
                        return legnth


                    for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]:
                        R, C = r+dr, c+dc

                        if R in range(N) and C in range(N) and grid[R][C] == 0 and (R, C) not in visit:
                            q.append((R, C)) 
                            visit.add((R, C))                        

                legnth += 1

            return -1 

        return bfs(grid)