(Python3) - LeetCode (Hard) : 2290. Minimum Obstacle Removal to Reach Corner

https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid

dijkstra문제였습니다.

📕 풀이방법

📔 입력 및 초기화

grid 높이 height, 너비 width를 선언 후 적절히 초기화합니다.

📔 풀이과정

특정 r행 c열에 도착할 때의 시간이 가변적이므로 0-1 bfs는 사용이 불가합니다. 따라서 최소의 가중치 중심으로 경로를 먼저 탐색하기 위해 dijkstra함수를 구현해 사용합니다.

 

1. 방향을 위한 배열 dr, dc와 min heap인 pq, r행 c열에 방문한 시간 checked선언 후 시작점을 넣어주고 check해줍니다.

 

2. pq에서 현재 방문한 time, r행, c열을 pop해줍니다. 만약 현재 r행 c열이 도착지점이라면 현재 시간 time을 반환합니다.

 

3. checked[r][c]보다 현재 시간이 크다면 늦게 도착했으므로 비교할 필요가 없습니다. continue해줍니다.

 

4. 인접 4방향에 대해 탐색을 진행합니다.

  4-1. 현재 방향으로 다음 nr행 nc열을 구해줍니다. grid의 범위를 벗어난다면 conitnue해줍니다.

  

  4-2. nr행 nc열에 기다린다면 닿을 수 있습니다. 대기시간을 구해줍니다. grid[nr][nc] - time이 기다릴 수 있는 시간이며 왕복할 때마다 2씩 소요되므로  2로 나누어 떨어진다면 해당 좌표에 도착할 때 wait_time은 grid[nr][nc] - time이 됩니다.  남은 시간이 홀수라면 1을 뺀 시간에 도착할 수 있으므로 wait_time은 grid[nr][nc] - time - 1이 됩니다.

 

  4-3. 이로써 nr행 nc에 도착할 수 있는 시간 next_time은 time + 1 + wait_time이 됩니다. 이로써 다음 좌표 nr행 nc열로 이동할 수 있는지를 최적화해 탐색 가능합니다.

 

  4-4. 다음 좌표의 저장된 최소 시간이 next_time보다 크다면 checked배열을 해당값으로 갱신하고 최적 경로이므로 pq에 next_time 정보와 nr, nc좌표를 heappush해줍니다.

 

5. 모든 탐색을 진행했으나 도착하지 못한 경우 -1를 반환합니다.

📔 정답 출력 | 반환

시작점 0행 0열의 인접한 좌표 0행 1열, 1행 0열이 1보다 크다면 이동자체가 불가능하므로 -1을 bfs함수 실행 전 바로 반환합니다.

그 외에 dijkstra함수의 결과를 반환합니다.

---

📕 Code

📔 Python3

from heapq import heappop, heappush

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        height = len(grid)
        width = len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1

        def dijkstra():
            dr = [0,0,1,-1]
            dc = [1,-1,0,0]
            pq = []
            checked = [[0x3f3f3f3f]*width for _ in range(height)]
            checked[0][0] = 1
            heappush(pq, (0,0,0))
            while pq:
                time, r, c = heappop(pq)
                if r == height - 1 and c == width - 1:
                    return time
                if time > checked[r][c]:
                    continue
                
                for i in range(4):
                    nr, nc = r + dr[i], c + dc[i]
                    if not (0<=nr<height and 0<=nc<width):
                        continue
                    if (grid[nr][nc] - time) % 2 == 0:
                        wait_time = max(0, grid[nr][nc] - time)
                    else:
                        wait_time = max(0, grid[nr][nc] - time - 1)
                    next_time = time + 1 + wait_time
                    if checked[nr][nc] > next_time:
                        checked[nr][nc] = next_time
                        heappush(pq, (next_time, nr, nc))
            return -1
        return dijkstra()

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.