[프로그래머스/Level 2] 배달 (C++)

programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

다익스트라 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 1번 정점에서의 각 정점까지의 모든 최단 거리를 구하고, K보다 작거나 같은 정점의 개수를 구하면 됩니다.

 

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

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

void D(int node) {
    priority_queue<pair<int, int>, vector<pair<int, int > >, greater<pair<int, int > > > pq;
    pq.push({ 0, node });
    dist[node] = 0;
    
    while(!pq.empty()) {
        auto now = pq.top();
        int v = now.second;
        int e = now.first;
        pq.pop();
        if(dist[v] < e) continue;
        
        for(auto &g : graph[v]) {
            int next = g.first;
            int nextVal = e + g.second;
            if(dist[next] > nextVal) {
                dist[next] = nextVal;
                pq.push({ nextVal, next });
            }
        }
    }
}


int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    for(auto &r : road) {
        graph[r[0]].push_back({ r[1], r[2] });
        graph[r[1]].push_back({ r[0], r[2] });
    }
    
    for(int i = 1; i <= N; i++) {
        dist[i] = 2147000000;
    }
    
    D(1);
    
    for(int i = 1; i <= N; i++) {
        if(dist[i] <= K) answer++;
    }
    
    return answer;
}