[JS] Shortest Path in Binary Matrix

🔒 문제 (LeetCode 1091)

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.

Constraints:

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

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘 - BFS

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    const dir =[[-1,-1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
    
    const q = [[0, 0, 1]]; 
    while(q.length) {
        const [r, c, len] = q.shift();

        if(grid[r][c]) continue;
        
        if(r === n-1 && c === n-1) return len;
        
        grid[r][c] = 1;
        
        dir.forEach(([x, y]) => {
            const [nr, nc] = [r + x, c + y];
            if(nr >= 0 && nr < n && nc >= 0 && nc < n && !grid[nr][nc]) {
                q.push([nr, nc, len + 1]);
            }
        })
    }
    
    return -1;
};