[LeetCode] 2290. Minimum Obstacle Removal to Reach Corner

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

leetcode - Minimum Obstacle Removal to Reach Corner

문제 유형: 최단경로, 다익스트라, 다이나믹 프로그래밍

문제 난이도: Hard

 

문제

You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:

• 0 represents an empty cell,
• 1 represents an obstacle that may be removed.

You can move up, down, left, or right from and to an empty cell.

Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).

 

0-indexed의 m x n 2D정수배열 grid가 주어진다.

0은 빈 공간, 1은 장애물이 있는 공간을 말한다.

당신은 (0, 0)에서 (m-1, n-1)로 가야한다.

최소 없애야하는 장애물의 수를 구하시오.

빈 공간에서 당신은 인접한 상하좌우 빈공간으로 움질일 수 있습니다.

 

풀이

최단 경로를 응용하면 된다.

dp[i][j] = (0, 0)에서 (i, j)까지 가기 위한 최소 장애물 파괴 수라고 보면 된다.

그리고, 인접한 칸으로 이동할 때, 장애물이 있는 공간으로는 비용이 1인 것이라고 보고, 장애물이 없으면 비용이 0이라고 생각하면 된다.

dp테이블을 처음에는 큰 수로 채워넣고, [0][0]에 대해서는 0으로 시작한다.

최소 힙 기반의 우선순위 큐를 이용해서, 최소 비용의 브랜치부터 탐색을 우선시하며 새로운 탐색 경우의 수들을 계속 우선순위 큐에 넣는다.

만약 더 저렴한 방법이 있다면, 계속 갱신하면서 우선순위 큐에 넣는것이다.

 

즉, 인접한 칸이 장애물이라면 거리가 1, 빈 공간이면 거리가 0인 가중치 미로찾기를 한다고 생각하고, 다익스트라를 이용하면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

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

struct comp {
    bool operator()(const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
        if(get<0>(a) == get<0>(b)) return get<1>(a) < get<1>(b);
        return get<0>(a) > get<0>(b);
    }
};

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

        vector<vector<int>> dp(m, vector<int>(n, 1e9));
        dp[0][0] = 0;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, comp> pq;
        pq.push(make_tuple(0, 0, 0));

        while(!pq.empty()) {
            auto [removal, x, y] = pq.top();
            pq.pop();
            if(removal > dp[x][y]) continue;

            for(int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if(grid[nx][ny] + dp[x][y] < dp[nx][ny]) {
                    dp[nx][ny] = dp[x][y] + grid[nx][ny];
                    pq.push(make_tuple(dp[nx][ny], nx, ny));
                }
            }
        }

        return dp[m-1][n-1];
    }
};

// dp[i][j] = (i, j)까지 가는데에 최소 removal 수.