백준 5972번 택배 배송 (C++)

문제 링크 : https://www.acmicpc.net/problem/5972

5972번: 택배 배송

문제 요약

 

1. 현서는 헛간 1에 있고 찬홍이는 헛간 N에 있습니다.

2.각 헛간에는 소가 있습니다.

3. m개의 횟수만큼 a에서 b로가서 마주치는 소에게 주어야할 여물 c가 주어집니다.

4. 현서가 찬홍이에게 가기 위해 사용해야하는 최소한의 여물의 비용을 구하세요.

 

핵심 포인트

 

다익스트라를 활용해서 쉽게 풀 수 있는 문제입니다.

여물의 비용을 결국 최단거리 비용으로 생각하면 됩니다.

 

문제 풀이

 

1. input()함수를 구현하여 필요한 변수를 선언하고 값을 입력받습니다.

int n,m,from,to,dis;
vector<vector<pair<int,int>>> v;
vector<int> map;

void input(){
    cin >> n >> m;
    v.resize(n+1); // 1
    map.resize(n+1,987654321); // 2
    for(int i=0; i<m; i++){ 
        cin >> from >> to >> dis;
        v[from].push_back({to,dis}); // 3
        v[to].push_back({from,dis});
    }
}

(1) v는 소의 정보가 담긴 벡터입니다. 1부터 N번째 헛간까지 소가 존재하므로, v벡터는 n+1로 사이즈를 초기화합니다.

(2) map은 1번부터 N번까지 각각의 위치를 가기 위한 최단거리가 저장된 벡터입니다. 사이즈를 n+1로 초기화하되, 각 배열의 값은 int값의 최대값으로 초기화합니다.

(3) 양방향 벡터이므로 from과 to를 번갈아서 벡터에 저장합니다.

 

2. int dijkstra()함수를 구현하여 map[n]의 최소값을 구합니다.

int dijkstra(){
    int pos,next,dis,ndis; // 1
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 2
    map[1] = 0; // 3
    pq.push({1,0}); // 4
    while(!pq.empty()){ // 5
        pos = pq.top().first; // 6
        dis = pq.top().second;
        pq.pop();
        for(int i=0; i<v[pos].size(); i++){ // 7
            next = v[pos][i].first; // 8
            ndis = v[pos][i].second;
            if(map[next]>map[pos]+ndis){ // 9
                map[next] = map[pos]+ndis;
                pq.push({next,ndis});
            }
        }
    }
    return map[n]; // 10
}

(1) pos는 현재 위치, next는 다음 위치, dis는 현재 위치의 누적 여물, ndis는 다음 위치로 가기 위해 필요한 여물 입니다.

(2) 우선순위 큐를 구현하되, greater로 구현합니다. greater로 구현함으로써 1번부터 N번까지의 위치 중, 위치가 작은 숫자들이 가장 앞으로 저장됩니다. 때문에 숫자가 작은 위치부터 숫자가 큰 위치까지 누적 이동 거리를 혼선없이 구할 수 있습니다.

(3) map[1]은 시작 위치이므로 0으로 저장합니다.

(4) 큐에 {1,0}, 즉, 시작위치를 삽입합니다.

(5) 큐가 빌때까지 while문을 진행합니다.

(6) pos에 현재 큐의 위치를, dis에 현재 큐의 누적 거리를 저장합니다.

(7) for문을 v[pos]의 사이즈만큼 돌립니다. 즉, 현재 위치와 연결된 다음 위치의 갯수만큼 for문이 진행됩니다.

(8) next는 현재 위치와 연결된 다음 위치, ndis는 현재 위치와 연결된 다음 위치에 가기위해 필요한 여물의 비용입니다.

(9) 만약 map[next](=다음 위치까지 가기위해 누적된 여물의 비용)이 map[pos]+ndis(=현재 위치까지 도달하기 위해 필요한 누적 여물의 비용 + next에 가기위해 필요한 여물의 비용)일 경우, map[next]를 새로 갱신하고 큐에 다음 위치와 누적 여물의 비용을 삽입합니다.

(10) map[n]을 반환하여 n번째 헛간까지 가기위해 필요한 최소한의 여물을 반환합니다.

 

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

int n,m,from,to,dis;
vector<vector<pair<int,int>>> v;
vector<int> map;

int dijkstra(){
    int pos,next,dis,ndis;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    map[1] = 0;
    pq.push({1,0});
    while(!pq.empty()){
        pos = pq.top().first;
        dis = pq.top().second;
        pq.pop();
        for(int i=0; i<v[pos].size(); i++){
            next = v[pos][i].first;
            ndis = v[pos][i].second;
            if(map[next]>map[pos]+ndis){
                map[next] = map[pos]+ndis;
                pq.push({next,ndis});
            }
        }
    }
    return map[n];
}

void input(){
    cin >> n >> m;
    v.resize(n+1);
    map.resize(n+1,987654321);
    for(int i=0; i<m; i++){
        cin >> from >> to >> dis;
        v[from].push_back({to,dis});
        v[to].push_back({from,dis});
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    cout << dijkstra() << "\n";
    return 0;
}