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)

 

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)

 

최종 코드: BFS (큐) + visit(set) 사용

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # 이진행렬에서, 최단 거리
        # 0 은 이동가능, 8방향 검색
        # topleft(0,0) -> bottom-right(n-1, n-1) 로 이동
        # 끝까지 못가면, -1 리턴
        if not grid:
            return -1

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

        n = len(grid)
        directions = [(-1, -1), (-1, 0), (-1, 1),
                      ( 0, -1),          ( 0, 1),
                      ( 1, -1), ( 1, 0), ( 1, 1)]
        
        
        # bfs 이므로 큐 사용
        queue = deque()
        visit = set()

        # 시작점 추가
        queue.append((0, 0, 1)) # r, c, 거리
        visit.add((0, 0))

        while queue:
            r, c, length = queue.popleft()
            if r == n - 1 and c == n - 1: # 마지막점까지 왔으면
                return length

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visit:
                    queue.append((nr, nc, length + 1))
                    visit.add((nr, nc))

        return -1