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

이 문제는 gird의 top-left에서 bottom-right까지의 최단 경로의 길이를 구하는

문제이기 때문에 bfs를 사용하여 풀었습니다.

 

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function(grid) {
    // 이동 가능한 경로가 없기 때문에 -1을 리턴
    if(grid[0][0] === 1) return -1
    
    const len = grid.length
    const directions = [[-1,0],[-1,1], [0,1], [1,1], [1,0], [1,-1],[0,-1],[-1,-1]]
    const seen = Array.from(Array(len), ()=>Array(len).fill(false))
    seen[0][0] = true
    
    let queue = [[0,0]]
    let steps = 0
    
    // 현재 경로가 grid를 벗어나거나 0이 아닌경우를 체크
    const gridIsValid = (x,y) => {
        return x >= 0 && x < len && y >= 0 && y < len && grid[x][y] === 0
    }
    
    while(queue.length){
        const nextQueue = [] 
        steps++
        
        for(const [x,y] of queue){
            // grid의 bottom-right에 도달했으므로 steps 리턴
            if(x === len-1 && y === len-1) return steps
            
            for(const [dx,dy] of directions){
                const nx = x+dx, ny = y+dy
                
                if(gridIsValid(nx,ny) && seen[nx][ny] === false){
                    seen[nx][ny] = true
                    nextQueue.push([nx,ny])
                }
            }
        }
        
        queue = nextQueue
    }
    
    return -1 
};