[Leetcode 1091] Shortest Path in Binary Matrix

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

 

문제설명

• nxn으로 구성된 행렬 grid가 주어질 때, (0,0)에서 (n-1,n-1)로 가는 가장 짧은 길의 길이를 구해라. 갈 수 없으면 -1. 0으로 구성된 칸에만 갈 수 있다.

 

 

문제해결

• 가장 짧은 길이를 구하는 거니까 BFS 사용
• 방향 주의하자 ! 4방향이 아니라 8방향으로 주어짐
• 현재 위치 뿐만 아니라 현재 길이도 같이 저장하자. 현재 위치가 n-1이면 다온거니까 여기에 저장되어 있던 길이를 반환하면 된다. (BFS를 사용했으므로 가장 먼저 조건에 만족된 값이 가장 짧은 값!)
• (n-1, n-1) 위치에 도착하지 않았는데 더 이상 갈 곳이 없을 수도 있다. bfs 함수 마지막에 return -1을 해주자. 갈 수 있는 곳만 q에 추가되는데 중간에 q가 비었다는 것은 더이상 갈 곳이 없다는 뜻

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        from collections import deque
        def bfs(r, c):
            q = deque()
            q.append([r, c, 1])
            row_len = len(grid)
            col_len = len(grid[0])
            dr = [0, 1, 1, 1, 0, -1, -1, -1]
            dc = [1, 1, 0, -1, -1, -1, 0, 1]
            visit = [[False for _ in range(col_len)] for _ in range(row_len)]
            visit[r][c] = True

            while q:
                cur_r, cur_c, cur_n = q.popleft()
                if cur_r == row_len-1 and cur_c == col_len-1:
                    return cur_n
                for i in range(8):
                    next_r = cur_r + dr[i]
                    next_c = cur_c + dc[i]
                    next_n = cur_n + 1
                    if 0 <= next_r < row_len and 0 <= next_c < col_len:
                        if visit[next_r][next_c] == False:
                            if grid[next_r][next_c] == 0:
                                q.append([next_r, next_c, next_n])
                                visit[next_r][next_c] = True
            return -1

        if grid[0][0] == 0:
            return bfs(0,0)
        return -1