[LeetCode] Shortest Path in Binary Matrix 풀이 (Python)

[LeetCode] Shortest Path in Binary Matrix 풀이 (Python)

https://leetcode.com/problems/shortest-path-in-binary-matrix/

Shortest Path in Binary Matrix - LeetCode

 

문제 해설

(0,0) 지점부터 (n-1, m-1) 지점까지 가는데 지나는 칸 수를 구하는 문제이다.

각 칸은 0 이나 1 로 구성되어 있으며 0 으로 구성된 칸만 지나갈 수 있다.

 

간단하게 BFS 를 통해서 풀 수 있지만, 다른 문제와 다른점은 이 문제에서 한칸을 이동할 때 대각선 방향으로도 이동이 가능하다는 것이다.

 

크게 고민할 필요없이 대각선방향의 이동도 dx, dy 에 추가해서 한칸 이동할 때 대각선의 이동도 포함하면 된다.

 

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        
        dx = [0,0,1,-1,1,1,-1,-1]
        dy = [1,-1,0,0,1,-1,1,-1]
        
        n = len(grid)
        m = len(grid[0])
        queue = deque()
        count = 0
        
        if (grid[0][0] == 0):
            queue.append([(0,0), count])
            grid[0][0] = 1
        
        while (queue):
            [pos, cnt] = queue.popleft()
            if (pos[0] == n - 1 and pos[1] == m - 1):
                return cnt + 1
            for _ in range(8):
                newY = pos[0] + dy[_]
                newX = pos[1] + dx[_]
                
                if (0 <= newY < n and 0 <= newX < m and grid[newY][newX] == 0):
                    queue.append([(newY, newX), cnt + 1])
                    grid[newY][newX] = 1
        return -1