NeetCode Islands and Treasure (JavaScript), BFS

링크 : https://neetcode.io/problems/islands-and-treasure/question

문제 설명

You are given a m×nm×n 2D grid initialized with these three possible values:

1. 1 - A water cell that can not be traversed.
   • 0 - A treasure chest.
   • INF - A land cell that can be traversed. We use the integer 2^31 - 1 = 2147483647 to represent INF.

Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest then the value should remain INF.

Assume the grid can only be traversed up, down, left, or right.

Modify the grid in-place.

Example 1:

Input: [
  [2147483647,-1,0,2147483647],
  [2147483647,2147483647,2147483647,-1],
  [2147483647,-1,2147483647,-1],
  [0,-1,2147483647,2147483647]
]

Output: [
  [3,-1,0,1],
  [2,2,1,-1],
  [1,-1,2,-1],
  [0,-1,3,4]
]

Example 2:

Input: [
  [0,-1],
  [2147483647,2147483647]
]

Output: [
  [0,-1],
  [1,2]
]

Constraints:

m == grid.lengthn == grid[i].length1 <= m, n <= 100grid[i][j] is one of {-1, 0, 2147483647}

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] is one of {-1, 0, 2147483647}

---

문제 풀이

각 위치에서 보물까지의 최소거리를 구하는 문제로 BFS를 활용하면 문제를 해결

[ 핵심 아이디어 ]

각 좌표에서 보물까지의 최소 거리를 구하는 형태로 로직을 작성할 경우 O(N * N)의 시간 복잡도를 가진다. 결국 n이 커지게되면 시간 초과 오류가 발생한다.

따라서, bfs를 n번 반복하는게 아닌 1번만 반복하도록 로직을 구성하면 된다.

1번만 반복하도록 하기위해서 각 좌표에서 보물까지의 최소 거리를 구하는게 아닌, 각 보물 좌표에서 이동하면서 각 좌표에 최소 거리를 최신화 해주면 된다.

이렇게 되면 보물 위치에서 단 한번의 BFS로 모든 좌표의 보물까지의 최소거리를 구할 수 있다.

class Solution {
    /**
     * @param {number[][]} grid
     */
    islandsAndTreasure(grid) {
        const cols = grid.length;
        const rows = grid[0].length;
        const dirs = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1]
        ];
        const visited = new Set();
        const queue = [];

        for (let y = 0; y < cols; y++) {
            for (let x = 0; x < rows; x++) {
                if (grid[y][x] === 0) {
                    queue.push([y, x, 0]);
                    visited.add(`${y},${x}`);
                }
            }
        }

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

            for (const [dy, dx] of dirs) {
                const my = y + dy;
                const mx = x + dx;
                if (my >= 0 && my < cols && mx >= 0 && mx < rows && !visited.has(`${my},${mx}`) && grid[my][mx] !== -1) {
                    visited.add(`${my},${mx}`);
                    queue.push([my, mx, cnt + 1]);
                }
            }
        }
    }
}

---

결론

BFS 형태의 문제이지만 BFS를 어떻게 활용할 건지에 대한 고민이 필요한 문제같다.