[C++] 백준 10217 - KCM Travel(다익스트라 활용)

0. [c++] 백준  -

https://www.acmicpc.net/problem/

1. 풀이

다익스트라 알고리즘을 활용해서 문제를 해결해보았다.

기본적인 다익스트라와 다르게 2개의 데이터를 활용해서 해결해야 하는 특수한 점이 있었다.

따라서, 변형을 한 후 문제에 적용이 필요했었는데, 나같은 경우에는 2차원 배열을 만들어서 문제를 해결하였다.

코드에서 timeDelay[101][10001]부분에 해당하는데, 위와 같이 설계를 하여서 다른 위상에 있는 값에서 탐색을 해 나갈 수 있도록 설계한 것이 포인트였다.

추가적으로 아래의 부분이 약간 특수한데, 

이걸 고려해준 이유는 

timeDelay[1][1] = 100;

timeDelay[1][100] = 10;

이라 가정하였을 때,

timeDelay[1][50] = 200; 이라는 데이터가 들어왔다 가정해보자.

이 데이터는 cost가 더 적은 1에서 이미 100의 timeDelay를 가지고 있는데, 이보다 더 큰 값을 가지고 있는 답을 구하는데 필요 없는 데이터이므로, 이러한 데이터가 중간에 들어가지 않도록 아래와 같은 처리를 해준 것이다.

if (timeDelay[there][nextCost] > nextTime) {

    for (int i = nextCost; i <= MAX_COST; i++) {

         if (timeDelay[there][i] > nextTime)

             timeDelay[there][i] = nextTime;

         }

    pq.push({ -nextCost, {nextTime, there} });

}

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#include<iostream> #include<vector> #include<queue> #include<algorithm>   using namespace std;   //앞에는 다음 공항, 뒤는 cost vector<pair<int, pair<int, int> > > idx[101]; const int INF = 1000000007; int timeDelay[101][10001];   void dijkstra(const int& N, const int& MAX_COST) {     for (int i = 0; i <= N; i++) {         for (int j = 0; j <= MAX_COST; j++)             timeDelay[i][j] = INF;     }     timeDelay[1][0] = 0;     priority_queue<pair<int, pair<int, int> > > pq;     pq.push({ 0, {0, 1} });     while (!pq.empty()) {         int cost = -pq.top().first;         int time = pq.top().second.first;         int here = pq.top().second.second;         pq.pop();         if (timeDelay[here][cost] < time)             continue;         for (int i = 0; i < idx[here].size(); i++) {             int nextCost = cost + idx[here][i].second.first;             int there = idx[here][i].first;             int nextTime = time + idx[here][i].second.second;                          //만일 최대 비용을 초과하는 가격이 나온다면, 패스한다.             if (nextCost > MAX_COST)                 continue;             //이 비용 위로 이 시간이 최소 시간이 되는지 확인하고, 미리 설정해준다.             //이유는, pq에 push를 최소로 하도록 만들어주고, 이미 들어간 값들의 무의미한 계산을 막아주기 위해서이다.             if (timeDelay[there][nextCost] > nextTime) {                 for (int i = nextCost; i <= MAX_COST; i++) {                     if (timeDelay[there][i] > nextTime)                         timeDelay[there][i] = nextTime;                 }                 pq.push({ -nextCost, {nextTime, there} });             }         }     }     int ret = INF;     for (int i = 1; i <= MAX_COST; i++)         ret = min(ret, timeDelay[N][i]);     if (ret == INF)         cout << "Poor KCM" << endl;     else         cout << ret << endl; }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       //T=테스트 케이스 수, N=공항의 수, M=지원 비용, K=티켓정보의 수     int T, N, M, K;     //u=출발공항, v=도착공항, c=비용, d=소요시간     int u, v, c, d;     cin >> T;     while (T--) {         cin >> N >> M >> K;         for (int i = 1; i <= N; i++) {             while (!idx[i].empty())                 idx[i].pop_back();         }         for (int i = 0; i < K; i++) {             cin >> u >> v >> c >> d;             idx[u].push_back({ v, {c, d} });         }         dijkstra(N, M);     }              return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!