[Lv 2] 배달

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

다익스트라 알고리즘을 사용하면 쉽게 해결할 수 있다.

 

road 배열 속 요소는 다익스트라 알고리즘을 사용하는데 불편하므로 

graph 배열 속에 요소를 새롭게 삽입한다.

for(int i = 0;i<road.size();i++){
        int a = road[i][0];
        int b = road[i][1];
        int c = road[i][2];
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }

 

요소를 새롭게 삽입한 이후, 우선순위 큐를 사용해 다익스트라 알고리즘을 구현한다.

 

다익스트라 알고리즘을 이용해 1번째 노드에 대한 최소 비용의 경로를 구했다면

1번노드에서 2, 3, 4, ... 번 노드로 이동할 때 K보다 작은 비용의 수를 구한다.

 

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

int dist[51];
vector<pair<int,int>> graph[51];

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    
    for(int i = 1;i<=N;i++)
        dist[i] = 987654321;
    for(int i = 0;i<road.size();i++){
        int a = road[i][0];
        int b = road[i][1];
        int c = road[i][2];
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    
    priority_queue<pair<int,int>> pq;
    pq.push({0, 1});
    dist[1] = 0;
    
    while(!pq.empty()){
        int cost = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        if(dist[now] < cost)
            continue;
        
        for(int i = 0;i<graph[now].size();i++){
            int next = graph[now][i].first;
            int nCost = graph[now][i].second;
            
            if(cost + nCost < dist[next]){
                dist[next] = cost + nCost;
                pq.push({-dist[next], next});
            }
        }
    }
    for(int i = 1;i<=N;i++){
        if(dist[i] <= K)
            answer++;
    }
    return answer;
}