23.03.05. 풀었던 문제들

Leetcode 1345. Jump Game IV

 어디선가 DP로 많이 본 문제. 첫 접근은 아래와 같이 dijkstra로 풀었다. 그러나 이 경우 for문 때문에 worst case $O(n^{2})$이 날 수 있다. 예를 들어 [1, 1, 1, 1, 1, 1, 1,1 ,1 ,1 ,1 ,1, 2]인 경우 1이 있는 부분을 계속 탐색하기 때문이다. dijkstra는 O(ElogV)인데, 위와 같은 경우 E가 $V^{2}$이 되기 때문이다.

typedef pair<int, int> pii; // .first : index, .second : dist
struct cmp{
    bool operator()(const pii&a, pii&b){
        if(a.second == b.second) return a.first > b.first;
        return a.second > b.second;
    }
};

class Solution {
public:
    
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        vector<int> dp(arr.size(), INT_MAX);
        map<int, vector<int>> m;
        for(int i = 0; i<n; i++){
            m[arr[i]].push_back(i);
        }

        priority_queue<pii, vector<pii>, cmp> pq; // 작은 게 top
        dp[0] = 0;    
        pq.push({0, 0});

        while(!pq.empty()){
            int idx = pq.top().first, dist = pq.top().second; pq.pop();
            if(idx + 1 < n && dp[idx + 1] > dp[idx] + 1){
                dp[idx+1] = dp[idx] + 1;
                pq.push({idx+1, dp[idx+1]});
            }
            if(idx - 1 > 0 && dp[idx - 1] > dp[idx] + 1){
                dp[idx-1] = dp[idx] + 1;
                pq.push({idx-1, dp[idx-1]});
            }
            for(int sameidx : m[arr[idx]]){
                if(dp[sameidx] > dp[idx] + 1){
                    dp[sameidx] = dp[idx] + 1;
                    pq.push({sameidx, dp[sameidx]});
                }
            }
        }

        return dp[n-1];
    }
};

 

 따라서 다른 방법으로 풀어야 한다. '최단거리'하면 나오는 건 BFS이다. 아래 코드가 정답 코드이다.

 일반적인 BFS이다. 그러나 [같은 수]에 대한 map을 저장했다. m[number]는 number에 해당하는 index들이다. 이것만 이용하면 위와 같이 계속 for(in i : m[arr[idx]])를 돌게 된다. 그러나 BFS의 정의에 따라 처음 마주쳤을 때 dist가 제일 짧다. 두 번째 탐색부터는 for(in i : m[arr[idx]])를 순회하지 않아도 된다. 또한, [같은 수]를 순회하더라도 그 수가 이미 발견된 수일 수 있다. 이 경우에는 탐색하며 안 된다. 이 부분을 빼먹어서 틀렸다.

// Runtime 300 ms Beats 38.26%
// Memory 80.5 MB Beats 41.99%

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if(n == 1) return 0;

        vector<int> dp(arr.size(), -1); // -1 : unvisited
        map<int, vector<int>> m;
        map<int, bool> visited;
        for(int i = 0; i<n; i++){
            m[arr[i]].push_back(i);
            visited[arr[i]] = false;
        }

        queue<int> q; // BFS
        q.push(0);
        dp[0] = 0;

        while(!q.empty()){

            int idx = q.front(), dist = dp[idx]; q.pop();
            if(idx == n-1) break;
            // only unvisited
            if(visited[arr[idx]] == false){  // 실수 : map을 여러 번 탐색하면 안됨
                visited[arr[idx]] = true;
                for(int sameidx : m[arr[idx]]){
                    if(dp[sameidx] == -1){ // 실수 : 원래 탐색했던 건 탐색하면 안됨
                        dp[sameidx] = dp[idx] + 1;
                        q.push(sameidx);
                    }
                }   
            }
            
            if(idx + 1 < n && dp[idx + 1] == -1){
                dp[idx + 1] = dp[idx] + 1;
                q.push(idx + 1);
            }
            if(idx - 1 > 0 && dp[idx - 1] == -1){
                dp[idx - 1] = dp[idx] + 1;
                q.push(idx - 1);
            }
            
        }

        return dp[n-1];
    }
};

 

 어떻게 개선할 수 있을까? 일단 visited 배열은 굳이 필요 없을 것 같다. m.find()를 해서 있는 경우에는 for문을 돌리고 erase를 해 버리면 된다. 그러면 visited 배열만큼 메모리를 아낄 수 있을 것이다. 또, unordered_map을 사용하는 경우 접근에 O(1)이 걸리니 더 줄일 수 있을 것이다.

 갱신하니 메모리는 약 10MB를, 시간은 100ms 정도를 줄일 수 있었다!

// Runtime 181 ms Beats 97.86%
// Memory 73 MB Beats 76.87%

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if(n == 1) return 0;

        vector<int> dp(arr.size(), -1); // -1 : unvisited
        unordered_map<int, vector<int>> m; // 개선 : map -> unordered_map
        for(int i = 0; i<n; i++){
            m[arr[i]].push_back(i);
        }

        queue<int> q; // BFS
        q.push(0);
        dp[0] = 0;

        while(!q.empty()){
            int idx = q.front(), dist = dp[idx]; q.pop();
            if(idx == n-1) break;
            // 개선 : map에 있을 때만 find 이후 erase
            if(m.find(arr[idx]) != m.end()){
                for(int sameidx : m[arr[idx]]){
                    if(dp[sameidx] == -1){
                        dp[sameidx] = dp[idx] + 1;
                        q.push(sameidx);
                    }
                }   
                m.erase(arr[idx]);
            }
            
            if(idx + 1 < n && dp[idx + 1] == -1){
                dp[idx + 1] = dp[idx] + 1;
                q.push(idx + 1);
            }
            if(idx - 1 > 0 && dp[idx - 1] == -1){
                dp[idx - 1] = dp[idx] + 1;
                q.push(idx - 1);
            }
        }

        return dp[n-1];
    }
};

 

시간복잡도

 BFS의 시간복잡도는 O(V + E)이다. 이 문제에서 worst case E = $V^{2}$을 가지고 있지만 적절히 cutting해서 E = V로 만들었다. 따라서 O(n)

 

공간복잡도

 dp vector에 O(n), map vector에 O(n), queue에 O(n)이므로 O(n)이다.

 

 

기본에 충실하자! 이 문제처럼 graph로 표현할 수 있을 때

• edge weight가 있으면 dijkstra / bellman-ford / floyd-warshall
  • negative weight면 bellman-ford
• edge weight가 없으면 BFS
  • BFS는 visited한 경우, 또 visit하면 안 된다!

이라는 것을 기억하자! 또, 가능한 한 예외케이스를 많이 생각해 보자.