[C++]백준 - 10217번 문제

10217번: KCM Travel (acmicpc.net)

10217번: KCM Travel

 

10217번 : KCM Travel

---

각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.

초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.

각 공항들간 티켓가격과 이동시간이 주어질 때, 찬민이 인천에서 LA로 갈 수 있는 가장 빠른 길을 찾아 찬민의 대회 참가를 도와주자.

 

입력

---

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다. 이어서 K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착공항 v (1 ≤ u, v ≤ N, u ≠ v), 비용 c (1 ≤ c ≤ M, 정수), 그리고 소요시간 d (1 ≤ d ≤ 1,000) 가 공백으로 구분되어 주어진다. 인천은 언제나 1번 도시이고, LA는 언제나 N번 도시이다

 

 

출력

---

각 테스트 케이스당 한 줄에 찬민이 LA에 도착하는 데 걸리는 가장 짧은 소요시간을 출력한다.

만약, LA에 도착할 수 없는 경우 "Poor KCM"을 출력한다.

 

 

---

 

생각해 볼 점

---

다익스트라로 풀어봅시다.

 

이번에는 cost와 time을 고려해야하는 그래프입니다.

 

원래 다익스트라에 추가로 동적 프로그래밍 기법을 활용해서 풉니다.

 

이차원 배열 DP를 만들어서

 

DP[N][C] = 0에서 출발하여 N 노드까지 C만큼의 cost를 사용하여 도착한 거리의 최소값

 

이라고 정의하겠습니다.

 

다익스트라를 진행하면서 DP에 중간 결과를 계속 저장하고, 만약 Cost가 입력된 한계 비용보다 커지면 그 탐색은 중단합니다.

 

N-1번 째 노드에 도달하는 것이 목적이므로,

 

DP[N-1][i] 중에서 가장 작은 값이 답이 됩니다.

 

코드

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//<목적지, 코스트, 소요시간>
struct vcd
{
    int v;
    int c;
    int d;
};

//비교 함수
struct cmp
{
    bool operator()(vcd A, vcd B)
    {
        return A.d > B.d || (A.d == B.d && A.c > B.c);
    }
};

int main() 
{
    int T;
    scanf("%d", &T);
    for(int tc = 0; tc < T; tc++)
    {
        int N, M, K;
        scanf("%d %d %d", &N, &M, &K);
        
        //동적 할당
        vector<vcd> *graph = new vector<vcd>[N];
        int **dp = new int*[N];
        for(int i = 0; i < N; i++)
        {
            dp[i] = new int[M + 1];
            fill_n(dp[i], M + 1, 0);
        }
        
        //입력부
        for(int i = 0; i < K; i++)
        {
            int u, v, c, d;
            scanf("%d %d %d %d", &u, &v, &c, &d);
            u--; v--;
            
            vcd input;
            input.v = v;
            input.c = c;
            input.d = d;
            graph[u].push_back(input);
        }
        
        //시작점 지정
        priority_queue<vcd, vector<vcd>, cmp> pq;
        vcd f;
        f.v = 0;
        f.c = 0;
        f.d = 0;
        pq.push(f);
        
        //다익스트라
        while(!pq.empty())
        {
            int current = pq.top().v;
            int c_cost = pq.top().c;
            int c_time = pq.top().d;
            pq.pop();
            for(vcd next : graph[current])
            {
                int n_cost = c_cost + next.c;
                int n_time = c_time + next.d;
                //코스트 오버 시 스킵
                if(M < n_cost) continue;
                
                //갱신
                if(dp[next.v][n_cost] == 0 || n_time < dp[next.v][n_cost])
                {
                    dp[next.v][n_cost] = n_time;
                    vcd next_node;
                    next_node.v = next.v;
                    next_node.c = n_cost;
                    next_node.d = n_time;
                    pq.push(next_node);
                }
            }
        }
        
        int min_result = 200000000;
        for(int i = 0; i < M + 1; i++)
        {
            if(0 < dp[N - 1][i] && dp[N-1][i] < min_result) min_result = dp[N - 1][i];
        }
        
        if(min_result == 200000000) printf("Poor KCM\n");
        else printf("%d\n", min_result);
        
        for(int i = 0; i < N; i++) delete[] dp[i];
        delete[] graph;
        delete[] dp;
    }
	return 0;
	
}

 

그 외

---

별도로, pair보다 많은 3개 이상의 원소를 가진 데이터 타입을 pq에 넣으려면 struct를 이용하여 3개의 원소를 지닌 데이터 타입을 지정하면 됩니다.