[LeetCode] 1368. Minimum Cost to Make at Least One Valid Path in a Grid

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/

leetcode - Minimum Cost to Make at Least One Valid Path in a Grid

문제 유형: 최단 경로, 다익스트라

문제 난이도: Hard

 

문제

Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

• 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
• 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
• 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
• 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some signs on the cells of the grid that point outside the grid.

You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

 

grid (0, 0), 에서 (m-1, n-1)로 가야한다. grid[i][j]에서 1은 왼쪽, 2는 오른쪽, 3은 아래로, 4는 위로 가는 방향이란 의미이다.

당신은 셀의 값을 단 한번만 바꿀 수 있다.

최소비용의 바꾸는 수를 구하시오.

바꾸는데 드는 비용은 1로 고정이다.

 

풀이

화살표를 따지지 말고, 모든 인접한 곳을 갈 수 있다고 보장하고 대신 기존 화살표방향은 비용이 0인 다익스트라를 생각하면 쉽다.

방향 코드에 맞게 이동 비용을 알맞게 조정해주면 된다.

셀 방향을 바꿀 때 단 한번만 가능하다는데, 어차피 pq를 이용하면서 순회하면 다시 되돌아갈 일이 없다.

 

최종적인 cost[n-1][m-1]로 가면 된다.(나는 편의상 n x m이 m x n보다 편해서 이렇게 했다.)

 

코드

C++

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

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int dx[] = {0, 0, 0, 1, -1};
        int dy[] = {0, 1, -1, 0, 0};
        int n = grid.size();
        int m = grid[0].size();

        vector<vector<int>> cost(n, vector<int>(m, INT_MAX));
        cost[0][0] = 0;

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
        pq.push({0, {0, 0}});

        while (!pq.empty()) {
            auto [currCost, currPos] = pq.top();
            pq.pop();
            int x = currPos.first;
            int y = currPos.second;

            if (currCost > cost[x][y]) continue;

            for (int i = 1; i <= 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                int newCost = currCost + (i == grid[x][y] ? 0 : 1);

                if (newCost < cost[nx][ny]) {
                    cost[nx][ny] = newCost;
                    pq.push({newCost, {nx, ny}});
                }
            }
        }

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