[알고리즘] LeetCode 01 Matrix JS

개요

0과 1로만 이루어진 2차원 배열이 주어질때 1의 인덱스에서 0과 얼마나 멀리 떨어져있는지 각 원소마다 계산하는 문제이다. 이때 거리는 상하좌우의 거리로 계산한다

01 Matrix - LeetCode

 

풀이

처음 문제를 BFS로 접근했었다. 조금 많이 복잡하게 구현됐는데 흐름도를 통해 살펴보면 다음과 같다.

 

1. 2차원 배열을 탐색하기 위해 이중 for문을 돌린다
2. 그렇게 돌면서 0은 넘어가고 1의 위치에서 BFS를 통해 근처 0의 위치를 탐색한다.
3. 찾으면 종료하고 현재 위치를 0과 떨어진 거리로 바꾼다
4. 배열이 끝날때까지 반복한다.

이렇게 구현했을 때 테스트 케이스는 통과를 하길래 아 다행히 잘 풀었구나 생각을 했는데 시간 초과 에러가 발생했다. 

아무래도 레벨이 높아질수록 탐색해야하는 인덱스가 많아지게되니 그럴 것이다라고 예상은 했지만 어떻게 해결하면 좋을지는 잘 떠올리지 못했다. 

 

고민해봤을 때 이전 탐색했던 노드들을 메모이제이션 시켜서 거리를 더하는건가 생각했었는데 조건을 생각하는 부분에서 막혔다. 결국 시간초과로 Discuss를 참고했고 이때 1을 탐색하는게 아닌 0을 탐색하여 주변에 있는 것들을 전부 바꿔주는 방식으로 이해했고 훨씬 적게 탐사할 수 있다는 것을 알았다.

 

추가로 조건을 잘 확인해봐야겠다. 접근 자체는 틀리지않았지만 그래도 떠올릴 수 있었다는 점에서 살짝 부족했던거 같다.

var updateMatrix = function (mat) {
  const m = mat.length;
  const n = mat[0].length;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (mat[i][j] === 0) continue;
      const queue = [[i, j]];
      let level = 1;

      //BFS
      //이미 탐색한 곳에서 값을 찾아낸다.
      while (queue.length > 0) {
        const len = queue.length;
        for (let k = 0; k < len; k++) {
          const [cx, cy] = queue.shift();
          let flag = false;
          for (let l = 0; l < dy.length; l++) {
            const nx = cx + dx[l];
            const ny = cy + dy[l];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
              if (mat[nx][ny] === 0) {
                flag = true;
                break;
              } else queue.push([nx, ny]);
            }
          }
          if (flag) break;
          level += 1;
        }
      }

      mat[i][j] = level;
    }
  }
  return mat;
};

 

Discuss

 

확실히 그림으로 이해하면 쉬운거같다

https://leetcode.com/problems/01-matrix/solutions/1629356/bfs-solution-with-explanation-and-visualization-js/

 

/**
 * @param {number[][]} mat
 * @return {number[][]}
 *
 * 0으로 BFS를 돌린다.
 */
var updateMatrix = function (mat) {
  const m = mat.length;
  const n = mat[0].length;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  const queue = [];

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      //거리를 계산하기 위해 레벨도 넣는다
      if (mat[i][j] === 0) queue.push([i, j, 0]);
      else mat[i][j] = Infinity;
    }
  }

  while (queue.length > 0) {
    const curr = queue.shift();

    for (let i = 0; i < dx.length; i++) {
      const nx = curr[0] + dx[i];
      const ny = curr[1] + dy[i];
      const level = curr[2];

      if (nx >= 0 && nx < m && ny >= 0 && ny < n && mat[nx][ny] === Infinity) {
        mat[nx][ny] = level + 1;
        queue.push([nx, ny, level + 1]);
      }
    }
  }

  return mat;
};
// @lc code=end