LeetCode - Matrix (Javascript)

문제 설명

값이 1인 요소를 찾아, 해당 1의 위치에서 가장 가까운 0 까지의 거리를 셀에 담아서 반환하는 문제다.

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.

---

소스 코드

보기엔 쉬워 보여도 까다로운 문제였다…
이번 문제도 queue를 활용해서 풀었다.

const directions = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
];

const updateMatrix = (mat) => {
  const rowMax = mat.length;
  const colMax = mat[0].length;
  const queue = [];

  for (let i = 0; i < rowMax; i++) {
    for (let j = 0; j < colMax; j++) {
      if (!mat[i][j]) queue.push([i, j]);
      else mat[i][j] = Infinity;
    }
  }

  while (queue.length) {
    const [row, col] = queue.shift();
    for (let [moveRow, moveCol] of directions) {
      const nextRow = row + moveRow;
      const nextCol = col + moveCol;
      if (mat[nextRow] === undefined || mat[nextRow][nextCol] === undefined)
        continue;
      if (mat[nextRow][nextCol] <= mat[row][col]) continue;
      queue.push([nextRow, nextCol]);
      mat[nextRow][nextCol] = mat[row][col] + 1;
    }
  }
  return mat;
};

---

풀이 설명

숫자의 대소비교를 통해 queue에 이전 값 + 1을 해주면 된다.

위의 그림과 같이, 우선 반복문을 통해 0은 queue에 좌표값을 담아 push해주고, 1은 Infinity화 해준다.

그리고 다시 위의 그림과 같이, 0을 찾아 shift해주고 → 자신을 기준으로 4방면에 있는 숫자들과 대소비교를 한다. 이후 자신보다 큰 값이 있으면 현재값(0) + 1을 해당 셀(cell)에 대입해준다.

이후에는 [0,1], [0,2]는 모두 4방면이 자신(0)보다 같은 값들이기 때문에 폐기한다. 그리고 [1,1]의 경우, 자신의 아래 요소가 자신보다 크기 때문에 자신의 값(0)+1을 대입해준다.

주의할 점은, 이전에 1로 값이 치환됐던 [1,0]의 셀은 queue에 push된 상태다.

다시 shift를 통해 [1,0]의 작업을 처리해야 하는데, 현재 값은1인데 아래 방면의 요소의 크기가 Infinity이므로, 현재값(1) + 1을 대입해주면 [2,0] 셀의 값은 2가 된다.

---