[LeetCode] 542. 01 Matrix, Medium

1. 문제

• m x n크기의 2차원 배열이 주어질 때, 값이 1인 좌표에는 인접한 0과의 최소 거리를 저장 후 반환하라.

2. 해결

const row = [-1, 1, 0, 0];
const col = [0, 0, -1, 1];

function updateMatrix(mat: number[][]): number[][] {
    const queue = new Array();
    
    for(let i =0; i< mat.length; i++) {
        for(let j =0; j< mat[i].length; j++) {
            if(mat[i][j] === 0) {
                queue.push([i,j])
            } else {
                mat[i][j] = -1;
            }
        }
    }

    while(queue.length > 0) {
        const [x,y] = queue.shift();

        for(let i=0; i< 4;i++) {
            const adjustX = x + row[i], adjustY = y + col[i]
            if(adjustX >= 0 && adjustX < mat.length && adjustY >=0 && adjustY <mat[adjustX].length){
            
                if(mat[adjustX][adjustY] === -1) {
                    mat[adjustX][adjustY] = mat[x][y] + 1;
                    queue.push([adjustX, adjustY])
                }
            }
        }
    
    }
    
    return mat;
};

• 처음에는 1인 좌표부터 0을 찾아 1을 증가 시키는 뭐 그런식으로 접근했는데, 잘못된 접근이었다.
• BFS를 풀 때 방문 여부를 항상 고려해야 한다.
• 최초 모든 요소를 탐색해 1인 곳을 -1로 만들어 방문 여부를 체크하게 하고, 모든 0 좌표를 Queue에 담아 탐색위치를 정한다.
• 자신과 근접한 1이 존재하면, 그곳으로 BFS 탐색을 해 들어가면서, 요소를 +1 갱신해주면 된다.