[LeetCode] 3286. Find a Safe Walk Through a Grid (Python)

 

난이도: Medium

 

문제 설명

---

You are given an m x n binary matrix grid and an integer health.

 

You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).

 

You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.

 

Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1.

 

Return true if you can reach the final cell with a health value of 1 or more, and false otherwise.

 

문제 예제

---

Example 1:

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
Output: true
Explanation:
The final cell can be reached safely by walking along the gray cells below.

 

Example 2:

Input: grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
Output: false
Explanation:
A minimum of 4 health points is needed to reach the final cell safely.

 

Example 3:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
Output: true
Explanation:
The final cell can be reached safely by walking along the gray cells below.

Any path that does not go through the cell (1, 1) is unsafe since your health will drop to 0 when reaching the final cell.

 

제한 사항

---

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 2 <= m * n
• 1 <= health <= m + n
• grid[i][j] is either 0 or 1.

 

✏️ Solution(솔루션)

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        start_x, start_y = 0, 0
        
        if grid[start_x][start_y] == 1:
            health -= 1
            if health == 0:
                return False

        n = len(grid)
        m = len(grid[0])

        moves = [[0,1], [1,0], [0,-1], [-1,0]]
        visited = defaultdict(bool)
        visited[(start_x, start_y)] = True
        q = []
        heapq.heappush(q, (-health, start_x, start_y))

        while q:
            h, x, y = heapq.heappop(q)
            
            if x == n-1 and y == m-1:
                return True
            
            for move in moves:
                nx = x + move[0]
                ny = y + move[1]

                if 0 <= nx < n and 0 <= ny < m and not visited[(nx, ny)]:
                    visited[(nx, ny)] = True
                    if grid[nx][ny] == 1:
                        if -h > 1:
                            heapq.heappush(q, (h+1, nx, ny))
                        else:
                            visited[(nx, ny)] = False
                    else:
                        heapq.heappush(q, (h, nx, ny))

        return False

 

단순히 BFS로 푸는 것이 아닌 health를 관리하면서 경로를 찾는 것이 빡센던 것 같다.

 

deque를 사용하여 popleft()를 통해 일반적인 BFS를 돌렸을 때, 몇몇 테스트 케이스에서 실패하는 것을 확인했다.

 

visited에 영향이 있는 것 같았다. 이 문제는 최단 경로를 찾는 것이 아니기 때문에 health 큰 경로 부터 확인 하면 될 것 같았다.

 

그래서 deque를 쓰는 것이 아닌 heapq를 사용했고, 이를 통해 높은 health를 가진 경로를 먼저 탐색할 수 있었고 문제를 해결할 수 있었다.

---

3286. Find a Safe Walk Through a Grid