LeetCode - As Far from Land as Possible (Javascript)

문제 설명

섬(1)에서 가장 멀리 떨어져 있는 바다(0)를 구하는 문제다.

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Example 1:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Constraints:

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

---

소스 코드

생각보다 까다로운 문제였다.
처음에는 문제의 요구사항이 조금 불분명하다는 생각이 들어서 풀이 로직을 짜는데 조금 시간이 걸렸다.

// 전역 변수 (상,우,하,좌)
const directions = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

const maxDistance = (grid) => {
  let answer = -1;
  const queue = [];
  // 섬(1) 찾아서 섬의 좌표와 기본 거리를 queue에 담아준다.
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) {
      if (grid[row][col] === 1) queue.push([row, col, 1]);
    }
  }

  let x, y;
  while (queue.length) {
    for (let i = 0; i < queue.length; i++) {
      const [row, col, distance] = queue.shift();
      for (const [moveX, moveY] of directions) {
        x = row + moveX; // 움직인 x좌표
        y = col + moveY; // 움직인 y좌표
        if (grid[x] === undefined || grid[x][y] === undefined || grid[x][y])
          continue;
        queue.push([x, y, distance + 1]); // 움직인 곳이 바다면 해당 위치와 distance+1을 queue에 push
        answer = Math.max(answer, distance);
        grid[x][y] = -1; // 방문 표시
      }
    }
  }
  return answer;
};

---