LeetCode - Shortest Path in Binary Matrix (Javascript)

문제 설명

가장 빨리 우측 최하단에 도달하는 path의 길이를 구하는 문제다.

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

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

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

---

소스코드

이 문제도 조금은 난이도가 있었다.
하지만, queue를 사용해 “가장 먼저 rightBottom에 도착하는” 요소의 축적된 거리를 반환해주도록 접근하며 솔루션을 낼 수 있었다.

const directions = [
  [1, 1], // 우측 대각선 방향의 경우를 가장 먼저 탐색해봐야 한다.
  [0, 1],
  [1, 0],
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [1, -1],
  [0, -1],
];

const shortestPathBinaryMatrix = (grid) => {
  if (grid[0][0]) return -1;
  const length = grid.length;
  const queue = [{ coord: [0, 0], distance: 1 }];
  let nextX, nextY;

  grid[0][0] = 1;

  while (queue.length) {
    const {
      coord: [x, y],
      distance,
    } = queue.shift(); // 디스트럭처링
    if (x === length - 1 && y === length - 1) return distance;

    for (let [moveX, moveY] of directions) {
      nextX = x + moveX;
      nextY = y + moveY;
      if (
        grid[nextX] === undefined ||
        grid[nextX][nextY] === undefined ||
        grid[nextX][nextY]
      )
        continue;
      queue.push({ coord: [nextX, nextY], distance: distance + 1 });
      grid[nextX][nextY] = 1;
    }
  }
  return -1;
};

---

풀이 방법

먼저, 위와 같이 0의 값을 가진 셀(cell)에서 8방향으로 모든 요소들을 체크한다.

중요한 점은, 시간효율성을 위해 우측대각선 방향을 우선적으로 탐색해야 한다는 것이다. 그리고, 단순 우측 방향 이동과 단순 아랫 방향 이동이 그 다음의 탐색 우선순위가 된다.

그리고 위의 사진과 같이 우측 하단 대각선 방향을 우선적으로 탐색한 뒤에, 해당 위치의 좌표값(coord)과 기존 distance + 1을 한 값을 distance에 담아서 queue에 push 해준다.

그리고 우측 방향을 탐색한 뒤에, 다른 방향들은 더이상 탐색할 수 없으므로 다음 queue를 shift 해준다.

그러면 우측 최하단에 도달했기 때문에 반복문이 종료되고 현재까지의 distance: 3을 최종 반환해준다.

---