[LeetCode] 1091. Shortest Path in Binary Matrix

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

Shortest Path in Binary Matrix - LeetCode

코드

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        short_dist = 1234567890
        dx = [0,0,-1,1,-1,1,1,-1]
        dy = [1,-1,0,0,1,-1,1,-1]
        q = deque()
        n = len(grid)

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

        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True

        q.append((0,0,1))
        while q:
            x,y,d = q.popleft()
            if x == n-1 and y == n-1:
                short_dist = min(short_dist,d)
                break
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<n and 0<=ny<n:
                    if grid[nx][ny] == 0 and not visited[nx][ny]:
                        visited[nx][ny]==True
                        q.append((nx,ny,d+1))
        return short_dist

 

풀이

• 네방향 탐색에서 업그레이드 되어 대각선으로도 움직일 수 있다고 하므로, dx,dy에 대각선으로 움직이는 값도 넣어준다.
• 그리고 큐에 넣을때에는 좌표뿐만 아니라 해당 좌표까지의 거리를 넣어준다.
• 그리고 q.popleft() 직후 x,y가 목적지 좌표에 도달했을 경우 최단거리 값을 갱신해준다.