Leetcode 2812. Find the Safest Path in a Grid

문제

You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents:

A cell containing a thief if grid[r][c] = 1
An empty cell if grid[r][c] = 0
You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.

The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid.

Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).

An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.

The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.

0-indexed 2D 행렬 grid가 주어집니다. grid의 크기는 n x n이며, 각 칸 (r, c)는 다음을 의미합니다.

grid[r][c] = 1이면 도둑이 있는 칸입니다.
grid[r][c] = 0이면 빈 칸입니다.

당신은 처음에 (0, 0) 칸에 위치해 있습니다. 한 번 이동할 때마다 인접한 칸으로 이동할 수 있으며, 도둑이 있는 칸으로도 이동할 수 있습니다.

grid에서 어떤 경로의 안전도는, 그 경로에 포함된 모든 칸들 중에서 가장 가까운 도둑까지의 맨해튼 거리의 최솟값으로 정의됩니다.

(n - 1, n - 1) 칸까지 도달하는 모든 경로 중에서 가능한 최대 안전도를 반환하세요.

어떤 칸 (r, c)의 인접한 칸은 존재하는 경우 다음 네 칸 중 하나입니다.

(r, c + 1)
(r, c - 1)
(r + 1, c)
(r - 1, c)

두 칸 (a, b)와 (x, y) 사이의 맨해튼 거리는 다음과 같습니다.

|a - x| + |b - y|

여기서 |val|은 val의 절댓값을 의미합니다.

---

예시

Input

grid
1	0	0
0	0	0
0	0	1

Output

0

Explanation

(0, 0)에서 (n - 1, n - 1)까지 가는 모든 경로는 도둑이 있는 칸인 (0, 0)과 (n - 1, n - 1)을 지나게 됩니다.

따라서 어떤 경로를 선택하더라도 경로 위의 칸 중 하나는 도둑이 있는 칸이며, 도둑까지의 맨해튼 거리는 0입니다.

그러므로 가능한 최대 안전도는 0입니다.

---

제한

• $1 <= grid.length == n <= 400$
• $grid[i].length == n$
• grid[i][j] 는 0 또는 1이다.
• grid에 반드시 도둑 ( 1 )이 하나 이상 존재한다.

---

풀이

1. 모든 그리드의 점에 대해 최소값의 안전도를 구한다.

ROW = len(grid)
        COL = len(grid[0])


        safeness = [[float("inf")] * COL for _ in range(ROW)]
        q = deque([])

        d = [[0, -1], [-1, 0], [0, 1], [1, 0]]

        for r in range(ROW):
            for c in range(COL):
                if grid[r][c]:
                    q.append((r, c, 0))
                    safeness[r][c] = 0

        def is_bound(r: int, c: int) -> bool:
            if 0 <= r < ROW and 0 <= c < COL:
                return True

            return False

        while q:
            r, c, s = q.popleft()

            for dr, dc in d:
                tr, tc = r + dr, c + dc

                if not is_bound(tr, tc):
                    continue

                if safeness[tr][tc] > s + 1:
                    safeness[tr][tc] = s + 1
                    q.append((tr, tc, s + 1))

2. 다익스트라를 이용해 가능한 safe값의 최댓값을 구한다.

• 여기서 중요한점

1. 그리드의 한 부분이 다른 부분에서 왔을때 최대 safe값은 min(현재 safeness값, 들어온 노드의 safeness 값)
2. 이 값을 계속 증가하도록 갱신해 나간다 ( 최댓값을 구하는거니까 )

전체 코드

from typing import List
from collections import deque
from heapq import heappush_max, heappop_max, heapify_max


class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        ROW = len(grid)
        COL = len(grid[0])


        safeness = [[float("inf")] * COL for _ in range(ROW)]
        q = deque([])

        d = [[0, -1], [-1, 0], [0, 1], [1, 0]]

        for r in range(ROW):
            for c in range(COL):
                if grid[r][c]:
                    q.append((r, c, 0))
                    safeness[r][c] = 0

        def is_bound(r: int, c: int) -> bool:
            if 0 <= r < ROW and 0 <= c < COL:
                return True

            return False

        while q:
            r, c, s = q.popleft()

            for dr, dc in d:
                tr, tc = r + dr, c + dc

                if not is_bound(tr, tc):
                    continue

                if safeness[tr][tc] > s + 1:
                    safeness[tr][tc] = s + 1
                    q.append((tr, tc, s + 1))

        h = [(safeness[0][0], 0, 0)]
        best = [[0] * COL for _ in range(ROW)]
        best[0][0] = safeness[0][0]

        while h:
            s, r, c = heappop_max(h)

            for dr, dc in d:
                tr, tc = r + dr, c + dc

                if not is_bound(tr, tc):
                    continue

                next_s = min(s, safeness[tr][tc])

                if next_s > best[tr][tc]:
                    best[tr][tc] = next_s
                    heappush_max(h, (next_s, tr, tc))

        return best[ROW - 1][COL - 1]