[Leetcode] Shortest Path in a Grid with Obstacles Elimination 문제 풀이

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

Shortest Path in a Grid with Obstacles Elimination - LeetCode

 

문제 내용

장애물을 피해서 최단거리를 찾는 문제인데

k번 만큼 장애물을 제거하고 갈 수 있다.

그렇게 했을 때 최단거리를 구하는 문제

 

Example 1:

Input:

grid = [

[0,0,0],  

[1,1,0],

[0,0,0],  

[0,1,1],

[0,0,0]],

k = 1

Output: 6

Explanation: The shortest path without eliminating any obstacle is 10. 

The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

 

문제 풀이

최단거리를 구하는 문제로 bfs를 이용해서 풀었다.

bfs의 특징상 먼저 도착하는 지점이 최단거리가 된다.

 

k번 장애물을 지울 수 있는데

지워서 가는 거랑 지우지 않고 가는거랑 경로 중에 최단거리를 구해야한다.

같은 지점이라도 k=0 에 도착할 수도 있고 k=1 로도 도착할 수 있다.

그래서 dist 배열에 k갯수만큼 메모이제이션을 사용했다.

 

class Solution {
public:
    int dist[40][40][1600] = {0};
    
    int dy[4] = {-1, 0, 1, 0};
    int dx[4] = {0, 1, 0, -1};
    
    int shortestPath(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = grid[0].size();
        
        queue<tuple<int,int,int>> q;
        q.push(make_tuple(0, 0, 0));
        while(!q.empty()) {
            auto [y, x, cnt] = q.front();
            q.pop();
            
            if (y == n-1 && x == m-1) {
                return dist[y][x][cnt];
            }
            
            for (int i = 0; i < 4; ++i) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                if (ny == -1 || ny == n || nx == -1 || nx == m || dist[ny][nx][cnt])
                    continue;
                
                if (grid[ny][nx] && cnt < k && dist[ny][nx][cnt+1] == 0) {
                    dist[ny][nx][cnt+1] = dist[y][x][cnt] + 1;
                    q.push(make_tuple(ny, nx, cnt+1));
                }
                
                if (!grid[ny][nx]) {
                    dist[ny][nx][cnt] = dist[y][x][cnt] + 1;
                    q.push(make_tuple(ny, nx, cnt));
                }
            }
        }
        return -1;
    }
};