[리트코드] 1091 - Shortest Path in Binary Matrix

1091. Shortest Path in Binary Matrix

Medium

---

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

 

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

 

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

분류

배열, 너비 우선 탐색, 행렬

---

문제 풀이

문제 분석

이 문제는 N x N 크기의 이진 행렬(grid)에서 좌상단(0, 0)에서 우하단(N-1, N-1)까지 이동하는 최단 경로의 길이를 구하는 것입니다.

• 이동 조건: 값이 0인 칸만 이동할 수 있습니다.
• 연결 방식: 상하좌우뿐만 아니라 대각선까지 포함하는 8방향으로 이동 가능합니다.
• 경로 길이: 방문한 칸의 개수(시작점 포함)로 정의됩니다.
• 예외 처리: 시작점이나 도착점이 1이거나 경로가 없으면 -1을 반환합니다.

접근 방법

너비 우선 탐색(BFS, Breadth-First Search) 알고리즘을 사용합니다.

• 이유: BFS는 시작 노드에서 가까운 노드부터 차례대로 탐색하므로, 가중치가 없는 그래프에서 최단 경로를 보장합니다. 이 문제에서 모든 이동 비용은 1로 동일하므로 BFS가 적합합니다.
• 자료구조: 탐색 순서를 관리하기 위해 **큐(Queue, Python의 deque)**를 사용하고, 중복 방문을 막기 위해 **방문 배열(visited)**을 사용합니다.
• 상태 저장: 큐에는 현재 좌표 (x, y)와 **현재까지 이동한 칸의 수(cnt)**를 함께 저장합니다.

구현 설명

1. 초기 검증 및 변수 초기화

• 시작점 grid[0][0]이 1(장애물)인 경우 즉시 -1을 반환하여 불가능함을 알립니다.
• 행렬의 크기 n, m을 저장하고, 방문 여부를 기록할 2차원 배열 visited를 False로 초기화합니다.
• BFS를 위한 큐를 생성하고, 시작점 (0, 0)과 초기 거리 1을 넣은 뒤 방문 처리합니다.
• 8방향 이동을 위한 directions 리스트를 정의합니다. (상, 하, 좌, 우, 좌상, 우상, 좌하, 우하)

2. BFS 메인 루프 수행

• 큐가 빌 때까지 반복하며, 가장 앞의 원소 (x, y, cnt)를 꺼냅니다.
• 도착 확인: 현재 좌표가 목적지 (n-1, m-1)이면 현재까지의 거리 cnt를 반환합니다. BFS 특성상 처음 도착한 경로가 최단 경로입니다.

3. 8방향 이웃 노드 탐색 및 큐 삽입

• 8개의 방향 벡터 (dx, dy)에 대해 다음 좌표 (sx, sy)를 계산합니다.
• 유효성 검사: 다음 좌표가 행렬 범위 내에 있는지(0 <= sx < n, 0 <= sy < m), 아직 방문하지 않았는지(not visited[sx][sy]), 이동 가능한 칸인지(grid[sx][sy] == 0)를 모두 확인합니다.
• 조건을 만족하면 방문 처리(visited[sx][sy] = True) 후, 거리 1을 증가시킨 (sx, sy, cnt+1)을 큐에 추가합니다.

4. 탐색 종료 및 결과 반환

• 큐가 비워질 때까지 목적지에 도달하지 못하면 경로가 없는 것이므로 -1을 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(N²)
  • 최악의 경우 행렬의 모든 칸(N x N)을 한 번씩 방문합니다. 각 칸에서 8방향 탐색은 상수 시간(O(1))이므로 전체는 O(N²)입니다.
• 공간 복잡도: O(N²)
  • 방문 배열 visited가 N x N 크기로 필요합니다.
  • 큐 역시 최악의 경우 모든 칸을 저장할 수 있어 O(N²)의 공간을 사용합니다.

핵심 포인트

1. BFS의 최단 경로 보장 특성: 가중치가 동일한 그래프에서 첫 방문이 곧 최단 거리임을 이용했습니다.
2. 8방향 이동 처리: directions 리스트에 대각선 벡터까지 포함하여 상하좌우 외 이동을 간편하게 구현했습니다.
3. 시작점/도착점 즉시 체크: 시작점(0,0)이 막혀 있으면 탐색 없이 바로 -1을 반환하여 불필요한 연산을 줄였습니다.

풀이 코드

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] == 1:
            return -1

        n = len(grid)
        m = len(grid[0])
        visited = [[False] * m for i in range(n)]
        queue = deque()
        queue.append((0,0,1))
        visited[0][0] = True

        directions = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
        while queue:
            x,y,cnt = queue.popleft()
            if x == n-1 and y == m-1:
                return cnt

            for dx,dy in directions:
                sx,sy = x+dx,y+dy
                if 0 <= sx < n and 0 <= sy < m and not visited[sx][sy] and grid[sx][sy] == 0:
                    visited[sx][sy] = True
                    queue.append((sx,sy,cnt+1))

        return -1