LeetCode (C/C++, Java) 2290. Minimum Obstacle Removal to Reach Corner

https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/description/

---

풀이

처음엔 다익스트라처럼 우선순위 큐를 사용, 제거한 셀의 횟수가 가장 적은 것부터 탐색하며 답을 구했는데 시간이 너무 느렸다.

다른 사람의 풀이를 보니, deque를 사용해 현재 탐색 중인 셀이

비어있다면 해당 셀에서 제거 횟수가 올라가지 않으므로 큐의 앞에 넣고,

비어있지 않다면 제거 횟수가 올라가 큐의 뒤에 넣어 탐색 순서를 맞춰 주었다.

하나를 넣을 때마다 굳이 정렬할 필요가 없어서 해당 풀이가 훨씬 빨랐다.

---

C/C++ 코드

class Solution {
public:
    typedef pair<int, int> ii;
    int minimumObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        vector<vector<int>> removal(m, vector<int>(n, 1'000'000));
        removal[0][0] = 0;
        
        deque<ii> q;
        q.push_front({0, 0});

        int mv[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!q.empty()) {
            ii now = q.front();
            int r = now.first, c = now.second;
            q.pop_front();

            for (int i = 0; i < 4; i++) {
                int nr = r + mv[i][0], nc = c + mv[i][1];
                if (nr < 0 || m <= nr || nc < 0 || n <= nc || removal[nr][nc] <= removal[r][c] + grid[nr][nc]) continue;
                removal[nr][nc] = removal[r][c] + grid[nr][nc];
                
                // 현재 셀이 비어있을 경우
                if (grid[nr][nc] == 0)
                    q.push_front({nr, nc});
                    
                // 현재 셀을 제거해야 하는 경우
                else
                    q.push_back({nr, nc});
            }
        }
        return removal[m - 1][n - 1];
    }
};

 

Java 코드

class Solution {
    public int minimumObstacles(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        int[][] cnt = new int[row][col];

        for (int[] r : cnt)
            Arrays.fill(r, Integer.MAX_VALUE);

        int[][] mv = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        q.addFirst(new int[]{0, 0});
        cnt[0][0] = 0;
        while (!q.isEmpty()) {
            int[] now = q.pollFirst();
            int r = now[0], c = now[1];

            for (int i = 0; i < 4; i++) {
                int nr = r + mv[i][0], nc = c + mv[i][1];
                if (nr < 0 || row <= nr || nc < 0 || col <= nc || cnt[nr][nc] <= cnt[r][c] + grid[nr][nc]) continue;
                cnt[nr][nc] = cnt[r][c] + grid[nr][nc];
                
                // 현재 셀이 비어있는 경우
                if (grid[nr][nc] == 0)
                    q.addFirst(new int[]{nr, nc});
                    
                // 현재 셀을 제거해야 하는 경우
                else
                    q.addLast(new int[]{nr, nc});
            }
        }
        return cnt[row - 1][col - 1];
    }
}