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

https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/?envType=daily-question&envId=2024-11-28

0-1 bfs로 풀어본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

높이 height, 너비 width, 방향 탐색을 위한 배열 dr, dc를 선언 후 적절히 초기화합니다.

📔 풀이과정

bfs함수를 구현합니다.

1. 탐색에 우선순위를 주기 위해 push pop이 상수 시간 복잡도를 가지는 deque변수 dq를 선언 후 사용합니다.

 

2. 재방문하지 않기 위한 checked배열을 width * height만큼 2차원으로 선언해줍니다.

 

3. 시작점 0행0열 0번 벽을 부숨을 의미하는 tuple (0,0,0)을 dq에 넣어줍니다.

 

4. 시작점을 방문했으니 checked[0][0]을 1로 갱신합니다.

 

5. dq에 원소가 있는 동안 while loop를 수행합니다.

 

  5-1. dq에서 원소를 왼쪽에서 pop해 현재 r행 c열 부순 벽 개수 broke를 선언해 저장해줍니다.

 

  5-2. 도착지점 height-1행 width -1열에 도착했다면 현재까지 부순 벽의 개수 broke를 반환합니다.

 

  5-3. 4개의 인접한 nr행 nc열을 확인하기 위한 for loop를 수행합니다. 탐색할 때 벽은 최대한 덜 부수고 싶기 때문에 벽이 아닌 grid라면 먼저 탐색하기 위해 왼쪽으로 원소를 넣어줍니다. 벽이라면 최대한 늦게 탐색하기 위해 오른쪽으로 원소를 넣어줍니다. 

📔 정답 출력 | 반환

최소 1개의 경로가 있음이 보장되므로 정상적으로 동작시 while loop내에 도착지점에 대해 값을 반환할 것이므로 return문을 bfs함수에 끝에 달아 아무값 -1을 반환합니다.

---

📕 Code

📔 Python3

from collections import deque
class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        height = len(grid)
        width = len(grid[0])
        dr = [0,0,1,-1]
        dc = [1,-1,0,0]

        def bfs():
            dq = deque()
            check = [[0] * width for _ in range(height)]
            check[0][0] = 1
            dq.append((0,0,0))
            while dq:
                r, c, broke = dq.popleft()
                if r == height - 1 and c == width - 1:
                    return broke
                for i in range(4):
                    nr, nc = r + dr[i], c + dc[i]
                    if not (0<=nr<height and 0<=nc<width):
                        continue
                    if check[nr][nc] == 1:
                        continue
                    check[nr][nc] = 1
                    if grid[nr][nc] == 1:
                        dq.append((nr,nc,broke + 1))
                    elif grid[nr][nc] == 0:
                        dq.appendleft((nr,nc,broke))
            return -1
        
        return bfs()

---

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