[코테연습] 2290. Minimum Obstacle Removal to Reach Corner

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

 

문제 타입

• Graph Traversal: 그래프 탐색 알고리즘을 사용해야 하는 문제입니다.
• Shortest Path: 최단 경로를 찾기 위해 다익스트라 혹은 BFS를 활용합니다.
• Dynamic Programming (BFS variation): BFS 변형을 통해 장애물을 최소로 제거하는 경로를 찾는 문제입니다.

문제 분석

• 2D 그리드에서 좌측 상단에서 우측 하단으로 이동해야 합니다.
• 장애물(1)을 최소한으로 제거하며 이동하는 것이 목표입니다.
• 빈 칸(0)은 자유롭게 이동 가능하며, 각 칸은 상하좌우로만 이동할 수 있습니다.

문제 풀이

1. 0-1 BFS 사용:
   • 다익스트라 알고리즘의 간단한 형태로, deque를 사용하여 0-1 BFS를 수행합니다.
   • 장애물을 제거하지 않고 이동하는 경우 deque의 앞에 삽입, 제거하는 경우 뒤에 삽입하여 최적의 경로를 찾습니다.
2. 우선순위 큐를 사용한 다익스트라:
   • 각 위치의 장애물 제거 횟수를 우선순위 큐에 넣어 관리하는 방식으로 풀 수 있습니다.
   • 방문할 때마다 현재까지의 장애물 제거 횟수를 기반으로 최소 값을 갱신합니다.
3. 단순 BFS로 푸는 방법:
   • 각 칸마다 제거된 장애물 수를 기록하며 단순 BFS로 탐색합니다.
   • 큐에 다음 위치와 현재까지 제거한 장애물 수를 넣어 가장 빠르게 목적지에 도달할 수 있는 방법을 찾습니다.

> java

 

class Solution {
    public int minimumObstacles(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};

        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.removed-o2.removed);
        pq.offer(new Node(0,0,0));
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;

        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int x = node.x;
            int y = node.y;
            int removed = node.removed;

            if (x == n-1 && y == m-1) {
                return removed;
            }

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    if (grid[nx][ny] == 0) {
                        // 장애물이 없는 경우
                        pq.offer(new Node(nx, ny, removed));
                    } else {
                        // 장애물이 있는 경우, 제거하고 이동
                        pq.offer(new Node(nx, ny, removed + 1));
                    }
                }
            }
        }
        return -1;
    }

    class Node {
        int x, y, removed;
        public Node(int x, int y, int removed) {
            this.x = x;
            this.y = y;
            this.removed = removed;
        }
        public String toString(){
            return "["+this.x+", "+this.y+", "+this.removed+"]";
        }
    }
}

 

> python

 

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])

        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]

        pq = []
        heapq.heappush(pq, (0, 0, 0))  # (removed, x, y)
        visited = [[False] * m for _ in range(n)]
        visited[0][0] = True

        while pq:
            removed, x, y = heapq.heappop(pq)

            if x == n - 1 and y == m - 1:
                return removed

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                    visited[nx][ny] = True
                    if grid[nx][ny] == 0:
                        # 장애물이 없는 경우
                        heapq.heappush(pq, (removed, nx, ny))
                    else:
                        # 장애물이 있는 경우, 제거하고 이동
                        heapq.heappush(pq, (removed + 1, nx, ny))

        return -1