[Leetcode] 1293. Shortest Path in a Grid with Obstacles Elimination

문제

 

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

Shortest Path in a Grid with Obstacles Elimination - LeetCode

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

 

Example 1:

Input	Output
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1	6
Explanation:  The shortest path without eliminating any obstacle is 10. The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

 

 

문제풀이 코드

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n, b = len(grid), len(grid[0]), k
		
        # 최단거리로 가는 거리보다 k가 크다면 언제나 최단거리로 이동할 수 있음
        if k >= m + n - 3:
            return m + n - 2
            
        dx, dy = [0, -1, 0, 1], [1, 0, -1, 0]
        visited = set()
        def bfs():
            dq = deque()
            dq.append((0,0,b,0))
            
            while dq:
                x, y, crush, distance = dq.popleft()
                if x == m - 1 and y == n - 1:
                    return distance
                
                for i in range(4):
                    xx, yy = x + dx[i], y + dy[i]
                    if 0 <= xx < m and 0 <= yy < n and crush >= grid[xx][yy]:
                        if (xx, yy, crush-grid[xx][yy]) not in visited:
                            dq.append((xx, yy, crush-grid[xx][yy], distance+1))
                            visited.add((xx, yy, crush-grid[xx][yy]))
            return -1
        return bfs()

최단거리를 구하는 문제로 bfs로 문제 풀이

visited: 중복 방문을 방지하기위해 set으로 초기화

crush: 벽을 부술 수 있는 남은 횟수

distance: 출발지부터 현재 위치까지의 거리

1. deque에 x, y, 벽을 부술수있는 횟수, 거리를 초기값으로 세팅

2. 일반적인 bfs 로직에서 벽을 부술 수 있는 횟수가 현재위치의 값보다 크고

3. 방문한적이 없을 때 dq에 삽입해준다.

4. bfs가 종료되고 받는 return값을 반환해준다.