[백준 5972] - 택배배송(C++)[골드5]

📕문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i!= B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3  

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

📕입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

📕출력

첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다

 

🔎문제 해석

최소의 비용으로 출발지에서 도착지까지 가고싶다는 말이 문제에 있습니다. 
--> 다익스트라 알고리즘을 사용해서 문제를 풀어야 겠죠?

 

그렇다면 다익스트라 알고리즘은 무엇일까요?

https://jja2han.tistory.com/145

[알고리즘] 다익스트라(Dijkstra)알고리즘?

다익스트라 알고리즘에 대해서 작성한 글이 있어서 혹시 모르신다면 가서 읽어 보시고 해당 문제를 풀어보시는 것을 추천합니다.

다익스트라 알고리즘을 사용하지 않으면 무조건적으로(아마도) 시간초과를 맛보게 될 것입니다.

 

음.. 다익스트라 알고리즘을 간단하게 설명하자면

현재 방문한 선택지들 중에서 가장 최적의 비용으로 다음 방문지를 찾는..? 알고리즘이라고 생각하시면 됩니다.

 

🖥️코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <queue>
using namespace std;
vector<pair<int, int> > graph[50001];
vector<int>dist;
priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > >pq;
int n, m;
int answer = 0;
void funct(int start);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m; // n : 정점 , m : 간선 개수
    int a, b, c;
    dist.resize(n+1,INT_MAX);
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c)); // a -> b 의 값은 c 라는 뜻 , 기본적으로 undirect graph라서. 모두 처리
        graph[b].push_back(make_pair(a, c));
    }
    pq.push(make_pair(1,0));
    funct(1);
    cout << answer;
    return 0;
}
void funct(int start)
{
    // 모든 지점을 안들러도됨. 만약 행선지가 n이라면 거기서 종료를 하자.
    while (!pq.empty()) //pq에는 출발지와 그 비용이 들어감.
    {
        int start =pq.top().first;
        int cost = pq.top().second;
        pq.pop();
        if(start==n){ //도착지에 도착한다면 종료함.
            answer=cost;
            return;
        }
        for(int i=0; i< graph[start].size();i++){ //현재 출발지에서 갈 수 잇는 모든 경로를
            int next = graph[start][i].first;
            int nextcost = graph[start][i].second;

            if(dist[next]>cost+nextcost){ // 비용 업데이트 해주기.
                dist[next]=cost+nextcost;
                pq.push(make_pair(next,dist[next]));
            }
        }
    }
    
}

 

느낀 점

• 다익스트라 알고리즘을 한동안 풀지 않다가 오랜만에 푸니 헷갈렸다.
• 문제 자체는 다익스트라 알고리즘만 안다면 골드 난이도는 아니라고 생각한다