1091. Shortest Path in Binary Matrix (Array, Breadth-First Search, Matrix)

링크 - https://leetcode.com/problems/shortest-path-in-binary-matrix/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

가장 적은 횟수로 목적지까지 가는 문제이므로, BFS가 가장 적합한 알고리즘이 될 것이다. 

1. 먼저 (0,0)에서 거리를 1로 설정해서 grid에 업데이트 한 뒤, 좌표를 deque로 집어넣는다. 

2. deque에 popleft를 해서 얻은 좌표와 거리를 가지고 다음 탐색할 좌표를 정한다. 다음좌표는 grid안에 있으며, 현재 좌표와 달라야 하는 8가지 방향에 있는 좌표를 확인해야 하며 그 중 0인 값을 가지고 있어야 한다.

3. 조건에 맞는 좌표들을 deque에 집어넣는다. 거리는 현재 가지고 있는 값에 1을 더해야 할것이다.

4. 2,3번을 반복하다가 좌표가 (n-1, n-1)에 도달했을때의 거리값을 반환한다.

Code

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)

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

        x_delta = [-1, 0, 1]
        y_delta = [-1, 0, 1]

        queue = deque()
        queue.append((0, 0))
        grid[0][0] = 1
        while queue:
            x, y = queue.popleft()
            distance = grid[x][y]

            if x == n-1 and y == n-1:
                return distance

            for dx in x_delta:
                for dy in y_delta:
                    new_x = x + dx
                    new_y = y + dy

                    if 0 <= new_x < n and 0 <= new_y < n and (new_x != x or new_y != y) and grid[new_x][new_y] == 0:
                        queue.append((new_x, new_y))
                        grid[new_x][new_y] = distance + 1

        return -1

Complexity

Time Complexity: O(n) 우리는 많아도 n개의 0값을 가진 grid를 탐색하기 때문에 O(n)이 된다.

Space Complexity: O(n) 우리는 queue 많아야 n개의 좌표를 넣을 것이기 때문에 O(n)이 된다.