[Algorithm][LeetCode] 1293. Shortest Path in a Grid with Obstacles Elimination

처음으로 leetcode hard 문제를 풀었다.

BFS와 Memoization을 적용한 풀이다.

초반엔 구조체 만들어서 풀었지만, tuple과 tie라는 STL을 적용하니 훨씬 깔끔해졌다.

그리고 {}를 이용해 데이터를 묶어주면 tuple, vector형식으로 자동 변환해준다.

시간복잡도는 m * n * k, 즉 40*40*1600이다. 

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        vector<vector<vector<int>>> dp;       
        dp.assign(41, vector<vector<int>>(41, vector<int>(1601, 0)));
        
        int ms = grid.size(); 
        int ns = grid[0].size();
        int rb, cb, kb;
        int cnt = 0;
        
        queue<tuple<int, int, int> > q;
        q.push({0, 0, k});
        
        while (!q.empty()) {
            tie(rb, cb, kb) = q.front();
            q.pop();
            int nb = dp[rb][cb][kb];
            
            if (rb == ms-1 && cb == ns-1) {
                continue;
            }
            if (rb < ms-1) {
                if (grid[rb+1][cb] == 1 && kb > 0) {
                    if (!dp[rb+1][cb][kb-1]) {
                        dp[rb+1][cb][kb-1] = nb+1;                     
                        q.push({rb+1, cb, kb-1});
                    }
                }
                else if (grid[rb+1][cb] == 0) {
                    if (!dp[rb+1][cb][kb]) {
                        dp[rb+1][cb][kb] = nb+1;
                        q.push({rb+1, cb, kb});
                    }
                }
            }
            if (cb < ns-1) {
                if (grid[rb][cb+1] == 1 && kb > 0) {
                    if (!dp[rb][cb+1][kb-1]) {
                        dp[rb][cb+1][kb-1] = nb+1;
                        q.push({rb, cb+1, kb-1});                        
                    }
                }
                else if (grid[rb][cb+1] == 0) {
                    if (!dp[rb][cb+1][kb]) {
                        dp[rb][cb+1][kb] = nb+1;
                        q.push({rb, cb+1, kb});                        
                    }
                }
            }
            if (rb > 0) {
                if (cb == 0)
                    continue;
                if (grid[rb-1][cb] == 1 && kb > 0) {
                    if (!dp[rb-1][cb][kb-1]) {
                        dp[rb-1][cb][kb-1] = nb+1;
                        q.push({rb-1, cb, kb-1});                        
                    }
                }
                else if (grid[rb-1][cb] == 0) {
                    if (!dp[rb-1][cb][kb]) {
                        dp[rb-1][cb][kb] = nb+1;
                        q.push({rb-1, cb, kb});
                    }
                }
            }
            if (cb > 0) {
                if (rb == 0)
                    continue;
                if (grid[rb][cb-1] == 1 && kb > 0) {
                    if (!dp[rb][cb-1][kb-1]) {
                        dp[rb][cb-1][kb-1] = nb+1;
                        q.push({rb, cb-1, kb-1});                        
                    }
                }
                else if (grid[rb][cb-1] == 0) {
                    if (!dp[rb][cb-1][kb]) {
                        dp[rb][cb-1][kb] = nb+1;
                        q.push({rb, cb-1, kb});                        
                    }
                }
            }
        }
        
        int mini = 1601;
        for (int i = 0; i < 1601; i++) {
            if (dp[ms-1][ns-1][i] != 0)
                mini = min(mini, dp[ms-1][ns-1][i]);
        }
        
        if (ms == 1 && ns == 1)
            return 0;
        
        if (mini != 1601)
            return mini;
        else
            return -1;
    }
};