[백준][C++] 10217 KCM Travel

www.acmicpc.net/problem/10217

10217번: KCM Travel

 

 

 

알고리즘 종류

    - 다익스트라

 

 

 

사고 과정

    - 간선의 가중치가 다르고 최단 거리를 구하는 다익스트라 문제이다. 또한, 조건이 2개이다. 조건이 1개일 때는, 1차원 배열을 사용해서 문제를 해결했다. 이번에는 조건이 2개으므로 2차원 배열을 이용해보자. 

        * dp[i][j] = value : 시작점 1에서 i까지 가는데 최소비용 j으로 가는 최소 시간 value

 

    - 일반적으로 풀게 되면 100% 제출이 되지만 시간이 3000ms 정도의 시간이 걸린다. 이를 빠르게 하는 방법은 아래와 같다.

        * 이 부분을 보자.

            // 시간과 비용 조건 확인  
            if(next_cost <= m && next_time < dp[next][next_cost]){
                // 불필요한 시간 재설정  
                for(int j=next_cost+1; j<=m; j++){
                    if(dp[next][j] <= next_time) break;
                    dp[next][j] = next_time;
                }
                
                dp[next][next_cost] = next_time;
                pq.push({-next_time, {next, next_cost}});
            }

 

        * next_cost=7, next_time=10이다. 그러면 dp[next][7] = 10이 된다. 그런데 아래 3개

            dp[next][8] = 12

            dp[next][9] = 15

            dp[next][12] = 16

            는 어떻게 처리해야할 것 같지 않은가?

        

            비용 내에서 최소 시간을 구하는 문제이다. 최소시간이 나왔으면, 그걸로 전부 바꿔주면 된다. 만약에 바꿔주지 않게 되면, pq에 최소 시간 보다 큰 시간이 들어가게 되서 연산량이 많아진다. 따라서 불필요한 시간을 최소 시간으로 재설정해준다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define INF  987654321
 
using namespace std;
 
int n, m, k;
 
struct Info{
    int node;
    int c, d;
};
 
vector<vector<Info> > edges;
int dp[101][10001];
 
void dijkstra(){
    
    priority_queue<pair<int, pair<int, int> > > pq;
    pq.push({0, {1, 0}}); // time, node, cost
    dp[1][0] = 0;
    
    while(!pq.empty()){
        
        int here = pq.top().second.first;
        int time = -pq.top().first;
        int cost = pq.top().second.second;
        pq.pop();
        
        if(dp[here][cost] < time) continue;
        
        for(int i=0; i<edges[here].size(); i++){
            int next = edges[here][i].node;
            int next_time = time + edges[here][i].d;
            int next_cost = cost + edges[here][i].c;
            
            // 시간과 비용 조건 확인  
            if(next_cost <= m && next_time < dp[next][next_cost]){
                // 불필요한 시간 재설정  
                for(int j=next_cost+1; j<=m; j++){
                    if(dp[next][j] <= next_time) break;
                    dp[next][j] = next_time;
                }
                
                dp[next][next_cost] = next_time;
                pq.push({-next_time, {next, next_cost}});
            }
        }
        
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int t;
    cin >> t;
    while(t--){
        
        cin >> n >> m >> k;
        // 배열 초기화  
        edges.clear();
        edges.resize(n+1);
        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++){
                dp[i][j] = INF;
            }
        }
        
        int u, v, c, d;
        for(int i=0; i<k; i++){
            cin >> u >> v >> c >> d;
            Info info;
            info.node = v;
            info.c = c;
            info.d = d;
            
            edges[u].push_back(info);
        }
 
        dijkstra();
        
        int answer = INF;
        for(int i=0; i<=m; i++){
            if(dp[n][i] < answer)
                answer = dp[n][i];
        }
        
        if(answer == INF) cout << "Poor KCM" << endl;
        else cout << answer << endl;
    }
    
}
 

 

 

 

시행착오

    - 시간을 이분탐색으로 찾고 다익스트라 알고리즘에 넣는 시도를 했다. 테스트케이스와 50%까지 성공했지만 이후에는 진전이 없었다. 결국, 도움을 받기 위해서 검색을 진행했다. 그리고 이 분의 블로그에서 많은 도움을 얻을 수 있었다. 정말 간단했다. 조건 1개일 때 1차원 배열, 2조건 2개일 때 2차원 배열을 사용했다. 그리고 중요한 것을 배울 수 있었다. 속도 향상 방법이었다.