[LeetCode] 542. 01 Matrix

문제 출처: https://leetcode.com/problems/01-matrix/

01 Matrix - LeetCode

 

문제

m x n 이진 행렬 mat 에서, 각 셀에서 가장 가까운 0 까지의 거리를 반환하라.

 

두 인접한 셀 사이의 거리는 1 이다.

 

예제

 

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

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

 

풀이

주어진 행렬에서 0과 1의 가장 짧은 거리를 구하기 위해서 BFS 알고리즘을 사용하였다.

 

최초 주어진 행렬을 탐색하면서 0의 위치를 기록하고, 이후에 이 지점으로부터 BFS로 탐색을 해가며 인접한 셀의 거리를 업데이트하는 방식으로 문제를 해결하려고 한다.

 

아래의 코드는 주어진 mat 배열에서 0의 위치를 기록하는 코드이다.

var updateMatrix = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    
    const ans = new Array(m).fill(0).map(val => new Array(n).fill(Infinity));
    
    // mat 내에서 0 위치 기록
    const queue = [];
    for (let i = 0; i < m; i++) {       // i: row
        for (let j = 0; j < n; j++) {   // j: column
            if (mat[i][j] == 0) { 
                ans[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    
    // BFS 단계
    
    return ans;
}

이후, 언급한 것처럼 BFS를 수행하며, 거리 정보를 업데이트할 것이다.

 

각 셀에서는 행렬의 바운더리에 있지 않는 이상 상하좌우 4방향으로 이동(?)할 수 있다. mat[i][j]=0 인 지점부터 생각해보자. 이 지점에서 4방향을 바라보고, 만약 mat값이 1인 지점이 있다면 해당 지점의 거리를 1로 업데이트시킬 수 있다. 

 

이렇게 업데이트된 지점은 다시 자신의 주변 4방향의 인접 셀을 보고 mat값이 1이 있다면 해당 지점의 거리를 2로 업데이트시킬 수 있다. 업데이트하면서 만약 해당 지점에 이미 어떤 거리가 저장되어 있다면 현재 값과 비교하여 업데이트 여부를 결정해야 한다.

 

아래 코드는 위 과정에 맞게 BFS를 작성한 코드이다.

var updateMatrix = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    
    const ans = new Array(m).fill(0).map(val => new Array(n).fill(Infinity));
    
    // mat 내에서 0 위치 기록
    ...
    
    // BFS 단계
    const move = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    while (queue.length) {
        let [curRow, curCol] = queue.shift();
        
        for (let i = 0; i < 4; i++) {
            let nextRow = curRow + move[i][0];
            let nextCol = curCol + move[i][1];
            
            if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n) {
                if (mat[nextRow][nextCol] == 0) { continue; }
                
                if (ans[nextRow][nextCol] > ans[curRow][curCol] + 1) {
                    ans[nextRow][nextCol] = ans[curRow][curCol] + 1;
                    queue.push([nextRow, nextCol]);
                }
            }
        }
    }
    
    return ans;
}

최종 코드는 아래와 같다.

var updateMatrix = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    
    const ans = new Array(m).fill(0).map(val => new Array(n).fill(Infinity));
    const queue = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] == 0) { 
                ans[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    
    const move = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    while (queue.length) {
        let [curRow, curCol] = queue.shift();
        
        for (let i = 0; i < 4; i++) {
            let nextRow = curRow + move[i][0];
            let nextCol = curCol + move[i][1];
            
            if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n) {
                if (mat[nextRow][nextCol] == 0) { continue; }
                
                if (ans[nextRow][nextCol] > ans[curRow][curCol] + 1) {
                    ans[nextRow][nextCol] = ans[curRow][curCol] + 1;
                    queue.push([nextRow, nextCol]);
                }
            }
        }
    }
    
    return ans;
};

 

Github: 542.js

GitHub - opwe37/Algorithm-Study