백준(BOJ)_KCM Travel(10217번)_C++

확실히 어려운 다익스트라 문제였다.

이전까지 풀던 다익스트라 문제들은 고려해야 할 조건이 한 가지였다면

이 문제는 고려해야 할 조건이 시간, 비용 두 가지였다.

한 가지일 경우 보통 dist배열 같은 1차원 배열을 선언하여 이를 갱신하면서 답을 구했다.

두 가지일 경우는 비슷하게 2차원 배열을 사용하면 된다.

 

내가 선언한 time[i][j] 배열은 j만큼의 비용을 들여 1에서 i로 갈 때의 시간을 저장하는 배열이다.

약간 knapsap-problem 과 비슷하다고 생각하면 된다.

이 배열을 이용해서 각 지점에 대해 모든 비용에 대응되는 시간을 표현한다.

그러면 time[n]에 해당하는 1차원 배열에는 1에서 n으로 갈 때 모든 비용에 대한 시간들이 들어있고,

이 시간들 중 가장 작은 값을 선택하면 된다.

 

여기까지 생각이 도달하려면 우선 기본적인 다익스트라 방법으로 풀고 시간초과 혹은 메모리초과를 겪으면 된다.

하지만 저 2차원배열을 생각해내고 풀어도 또 시간초과를 겪을 수 있다. (내가 그랬다...)

for(int j = ccost + ncost + 1; j <= m; j++){
    if (time[next][j] <= ctime + ntime)
	    break;
    time[next][j] = ctime + ntime;
}

위 코드를 통해 시간 초과를 해결할 수 있다.

위 코드가 실행되는 시점은 다음으로 이동할 수 있는 조건을 통과한 지점을 만났을 경우이다.

따라서 ctime + ntime은 ccost + ncost 비용으로 next에 갈 때 가장 적은 시간이고, next로 가는 ccost + ncost 비용보다 큰 비용들에 대해서 ctime + ntime 으로 초기화해주면 된다.

그러면 어차피 가장 적은 시간으로 초기화하는 것이므로 필요없는 경우들을 제외시킬 수 있다.

 

그리고 이 코드를 사용하면 아래의 코드도 굉장히 중요한 역할을 한다.

if (time[cur][ccost] < ctime)
    continue;

dijkstra() 함수의 while 문 도중에 위치한 if 문이다.

위의 for문을 통해 time[i] 배열이 가장 적은 시간으로 초기화되었다고 가정해보자.

그런데 초기화되기 이전에 임의의 time[i][j]에 대한 경우가 큐에 들어가 있었다고 생각해보면

큐에 들어가고 시간이 초기화 되었으므로 이 큐가 while에서 pop되었을 때는 ctime이 time[i][j]보다 클 수도 있다.

이러한 경우는 정답이 절대 아니기 때문에 바로 제외시켜주면 된다.

 

 

이 모든 상황을 한 번에 이해하기는 어려울 수도 있으니 우선 자신만의 방식대로 풀어서

시간초과도 경험해보고 메모리초과도 경험해보고 여러가지 실패를 겪고난 후, 이 코드를 보면 코드들의 의도를 알 수 있을 것이다.

 

다른 분들은 우선순위 큐를 사용하신 분들도 계셨는데 내가 볼 때는 시간과 비용 중 어떤 것을 기준으로 할지 애매했다.

둘 중에 하나로 정해서 우선순위 큐를 사용하더라도 이는 절대적인 기준이 되지 못하고,

정답인 경우를 우선순위로 하는 확률이 그렇게 높지 않다고 판단했다.

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 2e9

using namespace std;

int t, n, m, k, answer;
vector<pair<int, pair<int, int>>> ticket[10001];
int time[101][10001];

void dijkstra(){
    //{현재위치, {누적비용, 누적시간}}
    queue<pair<int, pair<int, int>>> q;
    q.push({1, {0, 0}});
    time[1][0] = 0;

    while (!q.empty()){
        int cur = q.front().first;
        int ccost = q.front().second.first;
        int ctime = q.front().second.second;
        q.pop();

        if (time[cur][ccost] < ctime)
            continue;

        for(int i = 0; i < ticket[cur].size(); i++){
            int next = ticket[cur][i].first;
            int ncost = ticket[cur][i].second.first;
            int ntime = ticket[cur][i].second.second;

            if (ccost + ncost <= m && ctime + ntime < time[next][ccost + ncost]){
                for(int j = ccost + ncost + 1; j <= m; j++){
                    if (time[next][j] <= ctime + ntime)
                        break;
                    time[next][j] = ctime + ntime;
                }
                time[next][ccost + ncost] = ctime + ntime;
                q.push({next, {ccost + ncost, ctime + ntime}});
            }
        }
    }
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> t;
    while (t--){
        //init
        for(int i = 0; i < 101; i++)
            for(int j = 0; j < 10001; j++)
                time[i][j] = INF;
        for(int i = 0; i < 10001; i++)
            ticket[i].clear();
        answer = INF;

        //input
        cin >> n >> m >> k;
        for(int i = 0; i < k; i++){
            int u, v, c, d;
            cin >> u >> v >> c >> d;
            ticket[u].push_back({v, {c, d}});
        }
        
        //dijkstra
        dijkstra();

        //output
        for(int i = 0; i <= m; i++)
            answer = min(answer, time[n][i]);

        if (answer == INF)
            cout << "Poor KCM\n";
        else
            cout << answer << "\n";
    }
}