백준 10217번 - KCM Travel

 

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

10217번: KCM Travel

 

다익스트라 알고리즘을 응용하는 문제로

 

기본적인 정형화된 문제라기 보다는 생각을 깊이 해야 하는 문제이다.

 

예를 들어 1 번이 시작이고 5번(도착지라 가정)까지 COST 가 10 이하인 비용으로

 

최소 거리를 찾아야 한다고 가정해보자.

 

맨 처음으로 1 노드를 기준으로 인접한 노드의 COST 와 DISTANCE 를 탐색해준다.

 

또한 행렬표를 만들어서 특정 노드에서 특정 노드로 갈 경우에 

 

PRIORITY QUEUE 를 생성하여 d,c,v 순으로 ENQUE 해준다.

 

행렬표를 만들어서 열은 COST 값을 나타내고 각 행은 도착지 노드 번호를 나타낸다.

 

해당 행/열 데이터 내부에 들어가는 정보는

 

해당 도착지 노드로 가는 DISTANCE 가 입력된다.

 

기본행렬의 초기값은 모두 가장 큰 정수값을 할당해준다.

 

 

 

 

일단 PRIORITY QUEUE 를 생성해주고 첫번째 노드 1 에 대한 정보를 담아준다.

 

그럼 QUEUE 내부에는 아래와 같은 그림이 들어가게 되고 

 

(1,0) 행렬에는 아래와 같이 0으로 DISTANCE 값 자체가 초기화 된다.

 

 

 

 

 

첫번째 QUEUE 에서 뽑은 정보를 토대로 해석해보자. (0,0,1)

 

첫번째 QUEUE 에서 뽑은 정보는 NODE 1 에 인접한 노드 사이의 정보를

 

QUEUE 와 행렬에 기입해주는 것이다.

 

1 -> 5 로 바로가는 경로가 존재하지만, 대 전제인 COST가 10이하여야만 한다는 규칙을 어기므로

 

ENQUEUE 하지 않고 행렬정보에도 기입하지 않는다.

 

그래서 1->2, 1->3, 1->4 로 가는 경로의 정보만 QUEUE 에 집어넣어 준다.

 

 

 

이제 큐에서 차례차례로 데이터를 뽑고

 

해당조건을 만족하는 데이터를 넣어주는 작업을 수행해보자.

 

첫번째 QUEUE 에 있는 정보(2,6,4) 를 뽑아내주면 4 -> 5 로 가는 정보가 담겨있다.

 

4 노드에 도착하기 이전의 COST 와 DISTANCE 정보와 4 -> 5 노드로 이동하는

 

COST 와 DISTANCE 를 각각 더해준다.

 

(2,6,4) + (1,4,5) => (3,10,5)

 

그럼 (3,10,5) 즉, DISTANCE 는 3, COST 는 10 으로 대전제를 만족하므로

 

PRIORITY QUEUE 에 ENQUEUE 시켜준다.

 

우선순위 큐이므로 아래와 같이 바로 두번째 위치로 정렬되는 모습을 볼 수 있다.

 

 

 

두번째로 1 -> 3 -> 5 로 거쳐가는 영역을 조사해보자.

 

COST 가 8 DISTANCE 가 8 이므로 COST 가 10 이하인 대 전제를 만족한다.

 

하지만 행렬정보를 보면  (5,10) 에 현재 DISTANCE 값 8 보다 작은 3이 존재한다.

 

그러므로 해당 데이터를 QUEUE 에 ENQUEUE 해주지 않고,

 

행렬상에도 기존값으로 유지시켜준다.

 

 

 

위와 같은 방식으로 계속 진행하다 보면 아래와 같이 최종 행렬이 만들어질것이다.

 

예시에서 우리는 5가 목적지로 정해놨기 때문에 NODE 5 에 대한

 

모든 열을 탐색하여 최소값을 가져오면 

 

해당 값이 우리가 원하는 한계비용을 만족한 최소거리 값이 된다. 

 

아래 표에서는 NODE = 5 일때 6과 3 이 존재하므로

 

답은 가장 최소 distance인 3이 된다.

 

코드는 아래와 같이 짤 수 있다.

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

int INF = INT_MAX;
int T,N,M,K;
int ver_val[102][10002];
vector < pair< pair<int,int>,int> > map[102];

void dijkstra() {
    
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            ver_val[i][j] = INF;
        }
    }
    
   priority_queue< pair< pair<int,int> ,int> > pq;
   pq.push(make_pair(make_pair(0,0),1));
   ver_val[1][0] = 0;
   
   while(!pq.empty()) {
       int cur_u = pq.top().second;
       int cur_d = -pq.top().first.first;
       int cur_c = -pq.top().first.second;
       
       pq.pop();
       
       for (int i = 0; i < map[cur_u].size(); i++) {
            int new_u = map[cur_u][i].second;
            int new_d = map[cur_u][i].first.first + cur_d;
            int new_c = map[cur_u][i].first.second + cur_c;
            
            if (new_c > M) continue;
            else if (ver_val[new_u][new_c] > new_d) {
                ver_val[new_u][new_c] = new_d;
                pq.push(make_pair(make_pair(-new_d,-new_c),new_u));
            }
            
       }
   }
}

int main()
{
    cin >> T;
    
    while(T--) {
        cin >> N >> M >> K;
        
        for (int i = 0; i <= N; i++) {
            map[i].clear();
        }
        
        for (int i = 0; i < K; i++) {
            int u,v,c,d;
            cin >> u >> v >> c >> d;
            
            map[u].push_back(make_pair(make_pair(d,c),v));
        }
        
        dijkstra();
        
        int result = INF;
        
        for (int i = 0; i <= M; i++) {
            result = min(result,ver_val[N][i]);
        }
        
        if (result == INF) cout << "Poor KCM\n";
        else cout << result << "\n";
    }
    
    return 0;
}

 

 

 

하지만 위와 같은 알고리즘에는 비효율이 존재한다.

 

예를들어 아래와 같이 1로 시작해서 4를 거쳐 5에 도착하는 방법을 살펴보자

 

일단 4를 거쳐서 5로 가는 방법은 2 가지 방법이 존재한다.

 

 

1) 첫번째 방법

 

2) 두번쨰 방법

 

COST 는 두 경로 모두 10 이하이므로 조건을 만족한다.

 

하지만 첫번째 경로를 따라가는것이 DISTANCE 가 최소값이 된다.

 

 

즉, 두 경로는 4라는 지점을 지나가는데 , 만약 (4,2) 조건(첫번째 방법)에서 아래와 같이 행렬을

 

자신의 COST를 포함해 허용된 총 COST 열까지 현재 DISTANCE 값으로 채운다면

 

1 -> 3 -> 4 의 경로는 QUEUE 에 들어가지 않을 것이고

 

이것은 비효율을 해결하는 방법이 될 수 있다.

 

비효율을 해결한 코드는 아래와 같다.

 

 

1. C++

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

int T,N,M,K;
int INF = INT_MAX;
vector < pair < pair<int,int>,int > > map[102];
int dist_res[102][10002];
int min_val = INT_MAX;

void dijkstra() {

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            dist_res[i][j] = INF;
        }
    }

    priority_queue< pair< pair<int,int>,int > > pq;
    pq.push(make_pair(make_pair(0,0),1));
    dist_res[1][0] = 0;

    while(!pq.empty()) {
        int cur_u = pq.top().second;
        int cur_d = -pq.top().first.first;
        int cur_c = -pq.top().first.second;

        pq.pop();
        
        if (cur_u == N) min_val = min(min_val,cur_d);

        for (int i = 0; i < map[cur_u].size(); i++) {
            int next_u = map[cur_u][i].second;
            int next_d = map[cur_u][i].first.first + cur_d;
            int next_c = map[cur_u][i].first.second + cur_c;
            
            if (next_c > M) continue;
            else if (dist_res[next_u][next_c] > next_d) {
                for (int i = next_c+1; i <= M; i++) {
                    if (dist_res[next_u][i] < next_d) break;
                    dist_res[next_u][i] = next_d;
                }
                dist_res[next_u][next_c] = next_d;
                pq.push(make_pair(make_pair(-next_d,-next_c),next_u));
            }
        }
    }
}


int main()
{

    cin >> T;

    while(T--) {
        
        cin >> N >> M >> K;
        min_val = INF;

        for (int i = 0; i <= N; i++) {
            map[i].clear();
        }

        for (int i = 0; i < K; i++) {
            int u,v,c,d;

            cin >> u >> v >> c >> d;

            map[u].push_back(make_pair(make_pair(d,c),v));
        }

        dijkstra();

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

    return 0;
}

 

아래와 같이 성능이 꽤 많이 차이나는 것을 볼 수 있다.