프로그래머스 - 배달 ( 다익스트라 알고리즘 )

출처 : programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

고려사항

• 최단경로 알고리즘인 다익스트라 사용했다.
• 경로에 음수 간선, 음수 사이클이 없기 때문에 사용 가능하다!
  (밸만 포드 알고리즘은 가능!)
• 이 문제처럼 한 점에서 모든 다른 노드까지의 경로를 구하는데 사용한다.
  (플로이드 워셜 알고리즘은 모든 노드에서 모든 노드까지의 최단 경로!)
• dijk[] 배열을 INF로 초기화 해준다.
• 시작점 1까지의 거리는 0으로 해주고, pq 에 삽입한다.
• while문 안에서 가장 작은 가중치를 지닌 값과 그에 해당하는 도시 정보를 pq를 통해 얻는다.
• dijk[도시] 의 값이 지금 값보다 작거나 같을 때만 다음 로직을 수행한다.
• 해당 도시에 연결된 도시 정보들을 ad 에서 얻고,
  현재 값 + 간선 가중치를 더한 값이 dijk[다음도시] 보다 작으면,
  값을 업데이트 하고, 해당 정보를 pq 에 넣는다.
• pq가 빌 때까지 반복한다.
• 1에서 시작해서 다른 모든 노드까지 도착하는 최단 경로 값들이 dijk[]에 담겼으니
  k보다 작은 경우를 세어 준다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#define INF 1000000000
using namespace std;

int dijk[51];
map<int, vector<pair<int, int>>> ad;

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int from, to, w, cost, city, nextCity, nextCost;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for(int i=1;i<=N;++i){
        dijk[i] = INF;
    }
    
    for(vector<int> v : road){
        from = v[0];
        to = v[1];
        w = v[2];
        
        ad[from].push_back({to, w});
        ad[to].push_back({from, w});
    }
    
    pq.push({0, 1});
    dijk[1] = 0;
    
    while(!pq.empty()){
        cost = pq.top().first;
        city = pq.top().second;
        pq.pop();
        
        if(cost <= dijk[city]){
            for(pair<int, int> p : ad[city]){
                nextCity = p.first;
                nextCost = cost + p.second;
                
                if(nextCost < dijk[nextCity]){
                    dijk[nextCity] = nextCost;
                    pq.push({nextCost, nextCity});
                }
            }
        }
    }
    
    for(int i=1;i<=N;++i){
        if(dijk[i] <= K){
            ++answer;
        }
    }

    return answer;
}