[Leetcode] Shortest Path in Binary Matrix - BFS

1. 문제

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

 

2. 풀이

이 문제는 BFS 푸는게 가장 간단할듯하다.

가중치없는 bfs라서, matrix 좌표에 따른 현재 cost 계산해서 가는 방식으로 하면 될듯!!

 

1) 이진 매트릭스 크기랑 같은 방문확인 매트릭스를 구축하고, 8방향 이동가능해서 이동 반경을 설정한다(dx,dy).

2) stack은 [x, y, cost]를 저장해서 bfs로 순회할 수 있게 하는 스택이다.

3) 방문했는지, 안했는지 체크하면서 순회하며 이전 cost에 1씩 더해가며 계산한다.

4) 이 방법이 최단 거리를 보장하는 이유는, 최종 도착지를 만나면 멈추는데, 먼저 왔다는건 빠르게 왔다는 의미이기 때문이다.

 

 

## code ##

from collections import deque
import copy
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # bfs
        new_grid = copy.deepcopy(grid)
        n, m = len(grid), len(grid[0])

        dx = [1, 1, 1, 0, 0, -1, -1, -1]
        dy = [0, -1, 1, 1, -1, 0, -1, 1]

        stack = deque([[0, 0, 1]])

        for i in range(n):
            for j in range(m):
                new_grid[i][j] = False
        new_grid[0][0] = True

        while stack and grid[0][0] == 0 and grid[n-1][m-1]==0:
            cur = stack.popleft()
            if cur[0] == n-1 and cur[1] == m-1:
                return cur[2]
            for i in range(8):
                cur_x = dx[i] + cur[0]
                cur_y = dy[i] + cur[1]
                
                if 0<=cur_x<n and 0<=cur_y<m and not new_grid[cur_x][cur_y] and grid[cur_x][cur_y]==0:
                    new_grid[cur_x][cur_y] = True
                    stack.append([cur_x, cur_y, cur[2]+1])
        return -1