[JS] 01 Matrix

🔒 문제 (LeetCode 542)

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

 

🌊 입출력

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

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

 

---

 

🔑 해결

🌌 알고리즘 - BFS

matrix에 존재하는 모든 0에서 출발.

상하좌우 4방향을 모두 이동하며 1을 찾았을 때 거리를 검사하여 최솟값 찾기

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    const q = [];
    
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(!mat[i][j]) q.push([i, j, 0]);
            else mat[i][j] = Infinity;
        }
    }
    
    let dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    while(q.length) {
        const [r, c, cnt] = q.shift();
        
        mat[r][c] = Math.min(mat[r][c], cnt);
        
        dir.forEach(d => {
            const [nr, nc] = [r + d[0], c + d[1]];
            if(nr >= 0 && nr < m && nc >= 0 && nc < n) {
                if(mat[nr][nc] === Infinity) {
                    q.push([nr, nc, cnt + 1]);
                }
            }
        });
        
    }
    
    return mat;
};