알고리즘/PS - 백준

[백준 1162 - C++] 도로포장 : 다익스트라(Dijkstra)

excited-hyun 2021. 7. 5. 14:31
반응형

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

 

1162번: 도로포장

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하

www.acmicpc.net

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

 

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

 

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

 

예제 입력 1 

4 4 1

1 2 10

2 4 10

1 3 1

3 4 100

예제 출력 1 

1

 

풀이

이 문제는 DP와 다익스트라를 모두 사용하여 풀이하였다. (문득 DP를 쓴게 맞나 하는 의문이 갑자기 든다)

우선, 포장할 수 있는 최대 도로의 수가 21개로 다소 작다.

또한 하나의 도로에 대해서는 포장을 하는 경우와 포장을 하지 않는 경우 이렇게 두 가지가 있다.

이 때 cost[도시번호][포장도로수]의 배열에 출발 도시에서 현재 번호의 도시까지 포장 도로수로 오는 비용의 최솟값을 넣어준다!

 

 

1. 포장 할 수 있는 도로들을 입력 받으면서 우선 2차원 벡터(way)에 저장해 둔다.

2. dijkstra()함수를 호출하여 다익스트라 알고리즘을 이용해 최소 거리를 찾기 시작한다.

3. cost[][]배열을 모두 -1로 초기화한다.

4. 우선 순위 큐에 이동 비용=0과 시작위치=1, 포장 도로수=0 을 넣어준다.

5. 우선순위 큐가 빌 때 까지 우선순위 큐에서 pop한 현재 위치에서 이동 가능한 경로를 통해 이동하는 위치를 하나씩 구한다.

이때 그 경로를 포장할 수도 있고, 포장하지 않을 수도 있다.

따라서 현재 포장 수가 k보다 작은 경우엔 포장하는 경우와 포장 하지 않는 경우 모두를 우선순위 큐에 넣는다. (포장하는 경우엔 이동 비용이 0이다!!!!!)

그렇지 않은 경우엔 더이상 포장할 수 없으므로 포장하지 않는 경우만 넣는다.

6. 이 때 cost[도시번호][포장도로수]가 초기화했던 -1이거나 새로 구한 이동비용보다 큰 경우 cost[][]를 갱신해준다.

7. 우선순위 큐가 empty가 되어 다익스트라 탐색이 모두 완료 되면 cost[N][0]~cost[N][k]중 최솟값을 찾고 이것이 답이 된다.

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

int n, m, k;
long long int cost[10001][21];
vector<pair<int, int>> way[10001]; //pos, cost
priority_queue<pair<long long, pair<int, int>>> pq; //cost,pos,포장

long long int dijkstra(int start){
    int here, there;
    long long int here_c;
    long long int there_c;
    long long int min_c = -1;

    for(int j=1; j<=n; j++){
        for (int i=0; i<21; i++)
            cost[j][i] = -1;
    }
    
    cost[start][0] = 0;
    pq.push(make_pair(-0, make_pair(start, 0)));
    
    while(!pq.empty()){
        here_c = -pq.top().first;
        here = pq.top().second.first;
        int cnt = pq.top().second.second;
        pq.pop();
        
        if(here_c> cost[here][cnt])
            continue;
        
        for(int j=0; j<way[here].size(); j++){
            
            there = way[here][j].first;
            there_c = here_c + way[here][j].second;
            
            if (cnt < k) //포장O -> 이동 비용이 0
            {
                if(cost[there][cnt+1] == -1) {
                    cost[there][cnt+1] = here_c;
                    pq.push(make_pair(-here_c, make_pair(there, cnt+1)));
                }
                if (cost[there][cnt+1] > here_c) {
                    cost[there][cnt+1] = here_c;
                    pq.push(make_pair(-here_c, make_pair(there, cnt+1)));
                }
            }
            
            
            if (cost[there][cnt] > there_c || cost[there][cnt] == -1) //포장X -> 이동비용이 있음!
            {
                cost[there][cnt] = there_c;
                pq.push(make_pair(-there_c, make_pair(there, cnt)));
            }
            
            
        }
    }
    min_c = cost[n][0];
    
    for(int i=1; i<=k; i++){
        if(min_c > cost[n][i] && cost[n][i] != -1)
            min_c = cost[n][i];
    }
    return min_c;
}




int main (void){

    int a, b, cost;
    scanf("%d %d %d", &n, &m, &k);
  
    for (int i=1; i<=m; i++){
        scanf("%d %d %d", &a, &b, &cost);
        way[a].push_back(make_pair(b, cost));
        way[b].push_back(make_pair(a, cost));
    }
    

    printf("%lld\n",dijkstra(1));
    
}
728x90
반응형