LeetCode 1091번 Shortest Path in Binary Matrix

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

---

문제 파악

n x n binary matrix인 grid가 주어졌을 때, 출발지에서 목적지까지 도착하는 가장 빠른 경로의 길이를 반환하는 문제! 경로가 없다면 -1을 반환한다. 출발지는 맨위의 왼쪽 셀이고 목적지는 맨 아래의 오른쪽 셀이다. 값이 0인 셀만 지날 수 있고 셀은 8가지 방향으로 연결되어 있다.

접근 방법

주어진 행렬은 상하좌우, 대각선으로 연결된 암시적 그래프로 볼 수 있으며 한 번 이동할 때의 길이가 모두 1로 동일하다. BFS를 통해 순회를 진행한다면 레벨별로 탐색을 진행하기에 가장 먼저 목적지에 도달하는 경우가 최단 거리임이 보장된다. 만약 BFS를 끝까지 진행하는 과정에서 한번도 목적지에 도달한 적이 없다면 이는 불가능한 경우로 -1을 반환하게 된다.

기존에는 4방향의 문제는 접했지만 이번에는 대각선 방향도 추가된 8가지 방향이다. 이를 dr, dc에 추가하여 8가지 케이스로 만들고 이를 BFS로 처리해서 문제를 풀면 될 것 같다.

코드 구현

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # 기본 값 설정
        shortest_dist = -1
        row_len = len(grid)
        col_len = len(grid[0])
        visited = [[False] * col_len for _ in range(row_len)]
        dr = [0, 1, 1, 1, 0, -1, -1, -1]
        dc = [1, 1, 0, -1, -1, -1, 0, 1]

        # grid의 시작점이 1이고 도착점이 1이면 최단거리 리턴
        if grid[0][0] == 1 or grid[row_len - 1][col_len - 1] == 1:
            return shortest_dist

        # BFS 진행할 큐 선언
        queue = deque()
        
        # queue(x좌표, y좌표, 거리)
        queue.append((0, 0, 1))
        visited[0][0] = True
    
        # BFS 진행
        while queue:
            cur_r, cur_c, cur_dist = queue.popleft()

            # 만약 도착점이라면
            if cur_r == row_len - 1 and cur_c == row_len - 1:
                shortest_dist = cur_dist
                break

            # 8방향 탐색
            for i in range(8):
                next_r = cur_r + dr[i]
                next_c = cur_c + dc[i]
                if (0 <= next_r < row_len) and (0 <= next_c < col_len):
                    if grid[next_r][next_c] == 0:
                        if not visited[next_r][next_c]:
                            queue.append((next_r, next_c, cur_dist + 1))
                            visited[next_r][next_c] = True

        return shortest_dist