542. 01 Matrix

542. 01 Matrix

Medium

---

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.

 

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]]

 

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.

1에서 0까지의 거리를 구하는 문제입니다.

 

bfs 탐색 방식으로 문제를 풀었습니다.

queue에 모든 0의 위치 좌표와 거리 0을 초기에 푸시해 줍니다.

그리고 탐색을 하면서 방문한 곳이 아니라면 해당 좌표에 거리를 표시해 줍니다.

 

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
    let queue = []
    const m=mat.length, n=mat[0].length
    const directions = [[-1,0],[0,1],[1,0],[0,-1]] 
    const visited = Array.from({length:m},()=>Array(n).fill(false)) // 방문한 곳 체크
    
    // 그리드에서 유효한지 체크
    const gridIsValid = (x,y) => {
        return x>=0 && x<m && y>=0 && y<n && mat[x][y] === 1
    }
    
    // queue에 좌표랑 거리 푸시 
    for(let row=0; row<m; row++){
        for(let col=0; col<n; col++){
            if(mat[row][col] === 0){
                queue.push([row,col,0])
                visited[row][col] = true
            }
        }
    }
    
    // bfs 탐색
    while(queue.length){
        const nextQueue = [] 
        
        for(const [x,y,distance] of queue){
            for(const [dx,dy] of directions){
                const nx=x+dx, ny=y+dy
                
                if(gridIsValid(nx,ny) && !visited[nx][ny]){
                    mat[nx][ny] = distance+1
                    visited[nx][ny] = true
                    nextQueue.push([nx,ny,distance+1])
                }
            }
        }
        
        queue = nextQueue
    }
    
    return mat
}