[LeetCode] 1091 | Shortest Path in Binary Matrix | Python

---

문제 링크: https://leetcode.com/problems/shortest-path-in-binary-matrix/

---

문제

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

---

조건

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

---

내 풀이

(0, 0)부터 (N-1, N-1)까지 가야하므로 grid[0][0]이나 grid[-1][-1]이 1이면 도달할 수 없다.

이 경우는 빠르게 알 수 있으므로 알고리즘을 시작하기 전 -1을 리턴한다.

 

deque를 사용해서 BFS를 진행한다. 이렇게하면 시간을 줄일 수 있다.

que를 사용하기 떄문에 우리의 목적지 (N-1, N-1)에 도달하는 여러 방법들은 오름차순으로 que안에 정렬된다.

que를 왼쪽에서부터 pop을 진행할 것이므로 맨 처음 (N-1, N-1)이 나올 때 그때의 cur를 리턴하면 된다.

---

코드

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] == 1 or grid[-1][-1] == 1:
            return -1
        
        N = len(grid)
        visited = set()
        dx = [1, 1, 1, -1, -1, -1, 0, 0]
        dy = [0, 1, -1, 0, 1, -1, 1, -1]
        que = deque([(0, 0, 1)])
        
        while que:
            y, x, cur = que.popleft()
            
            if grid[y][x] == 1:     continue
            if (y, x) in visited:   continue
            if (y, x) == (N-1, N-1):
                return cur
            
            visited.add((y, x))
            
            for t in range(8):
                newY, newX = y+dy[t], x+dx[t]
                if 0 <= newY < N and 0 <= newX < N:
                    que.append((newY, newX, cur+1))
        
        return -1