[Medium] 542. 01 Matrix

문제

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.

 

풀이 과정

Infinity에 0이 아닌 값을 할당하고 각 0 값의 좌표를 대기열에 추가하는 새 matrix을 만든다. 

대기열이 비어 있지 않은 동안 주변 셀 각각에 대해 검사를 실행하려고 한다. 

주변 셀이 최적화되지 않은 경우 값을 업데이트하려고 한다. 

주변 셀의 좌표가 matrix에 없으면 다음 주변 셀로 계속 진행한다. 

그런 다음 최적화된 셀을 대기열에 넣는다.

• 대기열과 새로운 matrix, 업데이트된 matrix을 초기화한다 .
• 입력 matrix의 각 셀을 스캔한다.
  • 셀이 0이면 큐에 넣고 업데이트된 matrix에서 좌표를 0으로 할당한다. 셀이 0이 아니면 좌표를 무한대로 할당한다.
• 대기열이 비어 있지 않은 동안 실행되는 while 루프를 시작한다.
  • 큐에서 제거하고 좌표를 y 및 x 변수에 할당하고 값을 currentValue 변수에 할당한다.
  • 주변 셀을 각각 확인한다.
    • 주변 좌표가 matrix에 없으면 다음 주변 셀로 계속 진행한다.
    • 주변 값이 currentValue + 1보다 크면 currentValue + 1로 업데이트 한다. 업데이트된 셀의 좌표를 큐에 넣는다.
• matrix을 반환한다.

 

해결 코드

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
   
    let updatedMatrix = [];
    let newRow;
    let queue = [];
    const dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    
    for(let y = 0 ; y < mat.length; y++){
        (newRow = []).length = mat[0].length;
        updatedMatrix.push(newRow);
        for(let x = 0 ; x < mat[0].length ; x++){
            if(mat[y][x] === 0){
                queue.push([y, x]);
                updatedMatrix[y][x] = 0;
            }else {
                updatedMatrix[y][x] = Infinity;
            }
        }
    }
    
    while(queue.length){
        let [y, x] = queue.shift();
        let currentValue = updatedMatrix[y][x];
        for(let dir of dirs){
            if(
                y + dir[0] < 0 ||
                y + dir[0] >= mat.length ||
                x + dir[1] < 0 ||
                x+ dir[1] >= mat[0].length
            ){
                continue;
            }else if(updatedMatrix[y + dir[0]][x + dir[1]] > currentValue + 1){
                updatedMatrix[y + dir[0]][x + dir[1]] = currentValue + 1;
                queue.push([y + dir[0], x + dir[1]]);
            }
        }
    }
    return updatedMatrix;
}

 

최적화된 값을 가진 셀의 좌표만 대기열에 추가한다. 즉, 가능한 0에서 가장 짧은 거리가 할당된다. 우리는 0에서 시작하여 0에서 1로 주변 거리를 최적화한 다음 1에서 2로 주변 거리를 최적화하고 2에서 3으로 주변 값을 최적화하기 때문에 이것을 알고 있다. 이렇게 함으로써 우리는 최적화되지 않은 값을 셀에 조기에 할당하지 않도록 한다. 또한 유효한 셀만 대기열에 들어가도록 한다.

이 경우 레벨별로 또는 거리별로 이동하는 것이 BFS의 특성이다. matrix이나 그래프 문제에서 절대 최단 거리를 구해야 할 때마다 BFS를 상기해야 한다.

 

빅오 분석

시간: O (r * c)
- r * c는 행 곱하기 열이다.

 

공간: O (r * c)
대기열에 할당된 메모리는 행렬의 셀 수에 따라 확장된다. 하나의 1이 0으로 둘러싸인 matrix가 예시이다.

 

---

참고 사이트

https://medium.com/@silasburger/01-matrix-leetcode-javascript-walkthrough-3747f894092c

01 Matrix LeetCode — Javascript Walkthrough