leetcode 778 - Swim in Rising Water

https://leetcode.com/problems/swim-in-rising-water/

풀이

BFS로 현재 상태에서 갈 수 있는 다음 상태를 찾는다. 대신 최단 거리를 찾아야 하므로 현재 상태를 고를 때 모든 상태 중에 가장 좋은 상태를 뽑아야 한다. 가장 좋은 상태는 문제 정의 그대로 최소 시간이다. 

 

이렇게 필요한 { 시간, x좌표, y좌표 } 세 가지를 가지는 set 자료구조를 사용해서 다익스트라를 사용해서 목적지까지의 최소 시간을 구할 수 있다. 모든 위치에 $n^2$에 대해서 set에 insert / erase가 필요하기 때문에 시간 복잡도는 $O(n^2 log n^2)$이다.

 

 

코드

class Solution {
public:
    vector<vector<int>> dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    int swimInWater(vector<vector<int>>& grid) {
        int N = grid.size();
        set<tuple<int, int, int>> states;
        vector<vector<int> > res(N, vector<int>(N, -1));
        
        states.insert(make_tuple(grid[0][0], 0, 0));
        res[0][0] = grid[0][0];
        while(!states.empty()) {
            auto state = states.begin();
            auto [elevation, x, y] = *state;
            for(int i = 0; i < 4; i++) {
                int nextX = x + dir[i][0], nextY = y + dir[i][1];
                if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && res[nextX][nextY] == -1) {
                    res[nextX][nextY] = max(res[x][y], grid[nextX][nextY]);
                    states.insert(make_tuple(res[nextX][nextY], nextX, nextY));
                }
            }
            states.erase(state);
        }
        return res[N-1][N-1];
    }
};