[백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐

✏️ 문제 링크

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

1916번: 최소비용 구하기

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

1. 도시 A에서 도시 B까지 가는 거리 저장

s는 출발점 도시 번호, e는 도착점 도시 번호, w는 s에서 e로 가는데 소요되는 비용이다. 

using pii= pair<int, int>;
vector<pii> vec[1001];

while(M--){
        int s, e, w; cin>>s>>e>>w;
        vec[s].push_back({e, w});
}

2. 시작 지점에서 모든 정점으로의 최소 비용 거리를 찾는다. 

    2-1. 시작 초기화

dist[dept] =0;
priority_queue<pii> pq;
pq.push({dist[dept], dept});

    2-2. 시작 지점에서 각 정점까지의 최단 거리를 구한다

        int cur = pq.top().second;
        int distance = pq.top().first * -1; //dept에서 cur 정점까지 가는 cost
        pq.pop();
        
        if(dist[cur]<distance) continue; //이미 cost가 최소로 변경됨

🔼 우선 pq에서 가장 top에 있는 pair를 뺀다. pq에서 저장되어 있던 pair중 가장 cost가 작은 pair를 꺼내 vertex와 cost를 저장한다. 

만약 dist[cur]이 pq에서 꺼내온 cur의 cost보다 작다면 이미 해당 vertex에 대해서 최소 비용으로 계산이 된것을 뜻하기 때문에 방문이 됐다고 간주하고 넘어간다. 

예를 들어 처음 시작 정점과 연결된 vertex와 비용이 pq에 모두 들어간다. 

pq = ({-1, 4}, {-10, 5} ...) 와 같다고 치자!

만약 pq에서 4번 정점을 빼와서 계산을 하다보니 start-4-5로 가는 비용이 더 적어 dist[5]에 변화가 일어났다고 생각하면 pq는 아래와 같이 변화될 수있다. 

pq = ( {-4, 5}, {-10, 5} ...)

그럼 또 현재 dist[5]= 4이고 pq내에 있는 비용 4와 10은 조건에 의해서 아래 최소비용 계산을 진행하지 않는다. 그렇기 때문에 자연스럽게 이미 방문했던 vertex를 방문하지 않게 되는 것!

for(int i=0; i<vec[cur].size(); i++){
            int nxt=vec[cur][i].first; //cur 정점과 연결된 정점들
            int nxtdist = vec[cur][i].second + distance;
            //현재까지 dept에서 cur정점까지의 최소 거리와 
            //cur을 지나 nxt까지의 거리를 더한것 cur정점에서 nxt까지의 distance      
            // e.g) 1 -> 4(cur) -> 5(nxt)
            
            if(nxtdist<dist[nxt]){//만약 cur을 지나가는 것이 더 가깝다면
                dist[nxt]= nxtdist;
                pq.push({nxtdist*-1, nxt});//새롭게 갱신된 weight와 vertex
            }
        }

🔼 이제 cur과 연결되어 있는 정점들에 대해서 계산한다. 계산을 진행한다는 dept-> cur -> nxt의 비용이 더 적은지 dept-> nxt의 비용이 더 적은지 확인해보겠다는 얘기다. 

만약 dept에서 nxt까지 가는 비용이 10이었는데, cur을 지나 nxt를 가는 경우는 4라고 치쟈! 그러면 dist[nxt]를 업데이트 해주는것이다. dist[nxt]를 업데이트 한다는 것은 dept에서 nxt정점까지 가는 비용이 더 적어졌다는 얘기. 

 

   while(!pq.empty()){
        int cur = pq.top().second;
        int distance = pq.top().first * -1; //dept에서 cur 정점까지 가는 cost
        pq.pop();
        
        if(dist[cur]<distance) continue; //이미 cost가 최소로 변경됨 
        
        
        for(int i=0; i<vec[cur].size(); i++){
            int nxt=vec[cur][i].first; //cur 정점과 연결된 정점들
            int nxtdist = vec[cur][i].second + distance;
            //현재까지 dept에서 cur정점까지의 최소 거리와 
            //cur을 지나 nxt까지의 거리를 더한것 cur정점에서 nxt까지의 distance      
            // e.g) 1 -> 4(cur) -> 5(nxt)
            
            if(nxtdist<dist[nxt]){//만약 cur을 지나가는 것이 더 가깝다면
                dist[nxt]= nxtdist;
                pq.push({nxtdist*-1, nxt});//새롭게 갱신된 weight와 vertex
            }
        }
    }

3. 최단거리 출력!

이제 dist에 저장된 값들은 시작 지점으로부터 각 vertex까지의 최단 거리를 의미하기 때문에 dist[dest]를 해주면 결과가 출력된다. ^_^

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321
using pii= pair<int, int>;
vector<pii> vec[1001];
vector<int> dist(1001, INF);

void dijkstra(int dept){
    dist[dept] =0;
    priority_queue<pii> pq;
    pq.push({dist[dept], dept}); // 시작 weight, vertex
    
    while(!pq.empty()){
        int cur = pq.top().second;
        int distance = pq.top().first * -1; //현재까지 dept에서 cur 정점까지 가는 dist
        pq.pop();
        
        if(dist[cur]<distance) continue; //이미 distance가 최소로 변경됨 
        
        
        for(int i=0; i<vec[cur].size(); i++){
            int nxt=vec[cur][i].first; //cur 정점과 연결된 정점들
            int nxtdist = vec[cur][i].second + distance;
            //현재까지 dept에서 cur정점까지의 최소 거리와 
            //cur을 지나 nxt까지의 거리를 더한것 cur정점에서 nxt까지의 distance      
            // e.g) 1 -> 4(cur) -> 5(nxt)
            
            if(nxtdist<dist[nxt]){//만약 cur을 지나가는 것이 더 가깝다면
                dist[nxt]= nxtdist;
                pq.push({nxtdist*-1, nxt});//새롭게 갱신된 weight와 vertex
            }
        }
    }
}
int main(){
    int N, M; cin>>N>>M;//도시의 개수, 버스의 개수
    
    while(M--){
        int s, e, w; cin>>s>>e>>w;
        vec[s].push_back({e, w});
    }
    
    int dept, dest;
    cin>>dept>>dest;
    
    dijkstra(dept);
    
    cout<<dist[dest];
    
    return 0;
}

 

 

 

✏️ 참고 사이트

아래 사이트에 다익스트라 알고리즘에 대한 자세한 설명이 있다 😊

https://chanhuiseok.github.io/posts/algo-47/

알고리즘 - 다익스트라 알고리즘(Dijkstra’s algorithm) : 모든 정점까지의 최단 경로 구하기

 

 ⭐ if feedback and question : comment please⭐