LeetCode/787. Cheapest Flights Within K Stops

싸메다가 중국 사이트에서 좋은 풀이를 찾았다. 시간,공간 복잡도 분석은 물론이고 c++ 11 문법을 적극적으로 활용하고 있다. 개안한 기분이다.

1. DFS 시간 초과. 시간 초과이지만 이런 풀이도 가능하다는걸 알 수 있다.

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        
        g_.clear();
        
        //map에 다가 pair로 연결된 점과 비용 저장
        for(const auto& e : flights)
        {
            g_[e[0]].emplace_back(e[1], e[2]);
        }
        //visited를 저장할 벡터 선언
        vector<int> visited(n, 0);
        //처음 출발 src 도시 방문 표시
        visited[src] = 1;
        //return할 정답값 선언 및 최소값 갱신 위해 INT_MAX 대입
        int ans = INT_MAX;
        //K+1을 넣어주는 이유는 주어진 값이 애매하기도 해서 K+1을 넣으면 앞으로 2번 더 방문가능하고
        //0이 되는순간 끝내기 위함
        dfs(src, dst, k+1, 0, visited, ans);
        
        
        //K+1 번 이동해서 dst에 가지 못했으면 -1 return하고 도착했으면 갱신된 ans값을 반환한다
        return ans == INT_MAX? -1 : ans;
    }
    
private:
    unordered_map<int, vector<pair<int, int>>> g_;
    //dfs로 탐색
    void dfs(int src, int dst, int k, int cost, vector<int>& visited, int& ans)
    {
        //도착했으면 cost를 정답에 넣어준다.
        if(src == dst)
        {
            ans = cost;
            return;
        }
        //더 이상 갈 수 없고, 목표에 도달하지 못했으면 끝
        if(k==0) return;
        
        //src에서 갈 수 있는 점 추출하여 가기
        for(const auto& p : g_[src])
        {
            //방문한 곳이라면 skip
            if(visited[p.first]) continue;
            
            //굳이 갈 필요 없다면 안간다
            if(cost + p.second > ans) continue;
            
            //방문 표시
            visited[p.first] = 1;
            //dfs로 탐색.
            dfs(p.first, dst, k-1, cost + p.second, visited, ans);
            //탐색 했으면 다음 순번을 위해 방문표시 지운다
            visited[p.first] = 0;
        }
        
    }
};

2. BFS. 마찬가지로 시간 초과. 하지만 pair를 {} 로 넣는것과 vector에 push_back할 때에는 std::move를 이용한 emplace_back이 더 빠르다는걸 배웠다.

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        //정점 - (연결된정점,비용) 저장할 map생성
        unordered_map<int, vector<pair<int,int>>> g;
        //정점 및 간선 비용 저장
        for(const auto& e: flights)
            g[e[0]].emplace_back(e[1], e[2]);
        
        //정답 값
        int ans = INT_MAX;
        //bfs에서 사용할 queue
        queue<pair<int, int>> q;
        //첫번째 점 넣는다
        q.push({src, 0});
        //현재 몇 개의 점을 방문한 상태인가?
        int steps = 0;
        
        while(!q.empty())
        {
            //처음 시작에는 첫번째 점만 존재하니 size = 1
            int size = q.size();
            //모든 1차로 연결된 점 방문했으면 0돼서 빠져나옴
            while(size--)
            {
                //점 정보 저장
                int curr = q.front().first;
                //간선 정보 저장
                int cost = q.front().second;
                //pop
                q.pop();
                //현재 점이 목표라면 갱신
                if(curr == dst)
                    ans = min(ans, cost);
                //연결된 점들에 대해서
                for(const auto& p: g[curr])
                {
                    //굳이 멀리 돌아가는 거면 버린다.
                    if(cost + p.second > ans) continue;
                    //이동한 점의 정보 및 비용 갱신하여 queue에 저장
                    q.push({p.first, cost + p.second});
                }
            }
            //k만큼 위쪽의 while문이 돌았으면 k개의 점 탐색한것임.
            //steps == k+1 이라면 현재 k개의 점을 방문한 상태
            if(steps++ > k) break;
        }
        
        return ans == INT_MAX? -1 : ans;
    }
};

3. 벨만-포드 알고리즘. 한 정점에서 다른 정점으로 가는 최소 비용을 구하는 알고리즘이다.

constexpr이 등장하고 있다! 해당 객체나 함수의 리턴값을 컴파일 시에 알 수 있다는 의미이다. 그리고 컴파일 시에 값을 결정가능한 식을 상수식이라고 한다. 그 중 값이 정수인 상수식을 정수 상수식 이라한다.

int arr[size]; 가 컴파일 되기 위해선 size가 정수 상수식이어야 한다. 

즉, constexpr int size = 3; 를 전역으로 해주고 main내에서 int arr[size] 를 컴파일해보면 정상적으로 된다!

하지만 const의 경우에는 바꿀 수 없는 값이라는 정보만 있을뿐, 굳이 컴파일 시에 값을 알아야 할 필요는 없다는 한정자이다.

아무튼, 간단한 코드이니 이해도 쉽다. 따라가면 금방 컨셉을 알 수 있다.

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        constexpr int kInfCost = 1e9;
        //2차원 배열 생성. 초기화는 무지막지하게 큰 값으로.
        //행이 k+2인 이유는 k=1일때, 2번째 점이 dst이어야 하므로
        //0번째 행은 시작상태, 1번째 행은 1번째 이동점의 비용, 2번째 행은 2번째 이동점의 비용이다
        //즉, k+2해서 idx상으로 k+1이 우리가 원하는 값이다.
        vector<vector<int>> dp(k+2, vector<int>(n, kInfCost));
        //시작상태 비용 처리. 처음 있는 위치는 비용이 0이다.
        dp[0][src] = 0;
        
        //i는 현재src에서 출발하여 몇 번째의 정점인지 표기
        for(int i=1; i<=k+1; ++i)
        {
            //src위치로 1번 이동하면 가만히 있는 것이므로 비용은 0
            dp[i][src] = 0;
            //간선정보 추출
            for(const auto& p: flights)
            {
                //연결된 점으로 가는 비용 갱신. 만약, 기존 계산된 비용보다 다른 점을 거쳐온 비용이
                //더 싸면 갱신한다
                dp[i][p[1]] = min(dp[i][p[1]], dp[i-1][p[0]] + p[2]);
            }
        }
        
        return dp[k+1][dst] >= kInfCost? -1: dp[k+1][dst];
    }
};