[LeetCode] 2577. Minimum Time to Visit a Cell In a Grid

https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid/description/

leetcode - Minimum Time to Visit a Cell in a Grid

문제 유형: 최단 경로, 행렬, 그래프

문제 난이도: Hard

 

문제

You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].

You are standing in the top-left cell of the matrix in the 0th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.

Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.

 

m x n의 행렬 grid를 받는다. grid[i][j]는 (i, j)에 오려면 grid[i][j]만큼의 시간이 지나야함을 의미한다.

당신은 (0, 0)에서 시작한다.

(m-1, n-1)까지 가야한다.

각 초마다 최소 한 번은 움직여야 한다.

최소 시간을 구하시오.

 

풀이

다익스트라를 통해서 풀 수 있다.

우선순위 큐에 <진행된 시간, 행좌표, 열좌표> 형태로 넣을 것이다. 처음엔 {0, 0, 0}으로 넣는다.

base case로, 처음에 갈 수 있는 칸(0, 1), (1, 0)이 막혀있다면 갈 수 없다.

그게 아니라면, 결국 언젠가는 (m-1, n-1)에 도달할 수 있다.

 

우선순위 큐에서 튜플을 꺼내서, 만약 도착지점에 왔다면 튜플의 시간을 반환한다.

그게 아니라면, 인접한 칸들에 대해 다음을 계산한다:

인접한 칸에 대해 가는 추가 대기 시간 w를 구한다. (grid[nx][ny] - 현재시간)이 홀수라면, 기다림 없이 이동이 가능하다. 

무슨 뜻이나면... currTime = 3이고, grid[nx][ny] = 5라고 해보자. currTime이 4 이상이 되어야 grid[nx][ny]에 갈 수 있기 때문에, 한 번 다른 땅을 밟고 온다. 그러면 currTime = 5, grid[nx][ny] = 5인데,(nx, ny)로 이동하고 나면 다음 currTime = 6이 된다.

그러나, currTime = 4이고, grid[nx][ny]이면, 바로 갈 수 있다. 이 경우 다음 currTime은 5가 된다.

 

그러나, 현재 시간이 더 크다면, 현재 시간을 따라야 한다. 즉, 둘 중 더 큰값으로 해야 한다.

그래서(currTime+1, grid[nx][ny] + w)중 더 큰 값이 (nx, ny)를 갈때의 시간이다.

만약 nextTime이 기존 시간테이블의 값보다 작으면, 우선순위 큐에 넣고 시간테이블 값을 업데이트한다.

 

 

코드

C++

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 minimumTime(vector<vector<int>>& grid) {
        if(grid[1][0] > 1 && grid[0][1] > 1) return -1;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, 1e9));
        dist[0][0] = 0;

        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, comp> pq; // time, r, c
        pq.push({0, 0, 0});

        while(!pq.empty()) {
            auto [currTime, x, y] = pq.top();
            pq.pop();
            if(x == m-1 && y == n-1) return currTime;
            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;
                int w = ((grid[nx][ny] - currTime) & 1)? 0:1;
                int nextTime = max(currTime+1, grid[nx][ny] + w);

                if(nextTime < dist[nx][ny]) {
                    dist[nx][ny] = nextTime;
                    pq.push({nextTime, nx, ny});
                }
            }
        }
        return -1;
    }
};