[LeetCode] 2812. Find the Safest Path in a Grid

https://leetcode.com/problems/find-the-safest-path-in-a-grid/description/

leetcode - Find the Safest Path in a Grid

문제 유형 : bfs, 우선순위 큐, 다익스트라, 최단거리

문제 난이도 : Medium

 

문제

You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents:

• A cell containing a thief if grid[r][c] = 1
• An empty cell if grid[r][c] = 0

You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.

The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid.

Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).

An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.

The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.

 

2차원배열 grid가 n x n의 크기를 가진다.

grid[r][c] = 1이면, (r, c)에 도둑이 있다.

grid[r][c] = 0이면, (r, c)는 빈 칸이다.

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

 

(n-1, n-1)로 가야 한다.

도둑으로부터의 위협이 가장 적은 루트의 최대 안전점수를 구하시오.

당신은 상하좌우로 인접한 곳으로 이동할 수 있습니다.

각 칸의 안전점수는 가장 가까운 도둑의 위치로부터의 맨해튼 거리이다.

 

풀이

우선, 각 블럭의 안전점수를 구해야 한다.

그 뒤, 우선순위 큐를 이용한 최적화된 다익스트라 알고리즘을 통해서 가장 안전한 루트를 구할 것이다.

 

각 블럭의 안전점수는 다음과 같이 구할 수 있다:

bfs를 하는데, 처음에는 도둑이 있는 위치들을 큐에 넣는다. 그러고 상하좌우로 영역을 넓히면서 안전점수를 1씩 누적시킨다.

이전의 방문여부는 문제없다. 그저 이전의 안전점수보다 새로 업데이트할 안전점수가 더 낮다면 또 큐에 넣느면 된다.

처음에는 안전점수 행렬을 큰 수로 채워넣어주면 된다.

이제, 대응되는 안전점수 행렬을 만들었다.

 

이제, (0, 0)에서 우선순위 큐를 이용한 다익스트라 알고리즘을 이용하여 루트를 구해서 나온 점수를 구하면 된다.

루트의 점수는 경로에 있는 모든 셀들의 점수의 최소값이다.

 

코드

C++

class Solution {
private:
    vector<int> dx = {-1, 1, 0, 0};
    vector<int> dy = {0, 0, -1, 1};
public:
    void bfs(vector<vector<int>>& grid, vector<vector<int>>& score, int n) {
        queue<pair<int, int>> q;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j]) {
                    score[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        while(!q.empty()) {
            auto curr = q.front();
            q.pop();
            int s = score[curr.first][curr.second];

            for(int i = 0; i < 4; i++) {
                int nx = curr.first + dx[i];
                int ny = curr.second + dy[i];

                if(nx >= 0 && nx < n && ny >= 0 && ny < n && score[nx][ny] > s+1) {
                    score[nx][ny] = s+1;
                    q.push({nx, ny});
                }
            }
        }
    }

    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();

        if(grid[0][0] || grid[n-1][n-1]) return 0;

        vector<vector<int>> score(n, vector<int>(n, 1e9));
        bfs(grid, score, n);
        vector<vector<bool>> visited(n, vector<bool>(n, false));

        priority_queue<pair<int, pair<int, int>>> pq;
        pq.push({score[0][0], {0, 0}});

        while(!pq.empty()) {
            auto curr = pq.top().second;
            auto safe = pq.top().first;
            pq.pop();

            if(curr.first == n-1 && curr.second == n-1) return safe;
            visited[curr.first][curr.second] = true;

            for(int i = 0; i < 4; i++) {
                int nx = curr.first + dx[i];
                int ny = curr.second + dy[i];

                if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
                    int s = min(safe, score[nx][ny]);
                    pq.push({s, {nx, ny}});
                    visited[nx][ny] = true;
                }
            }
        }

        return -1;
    }
};