[프로그래머스 2레벨] 배달 (C++)

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

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

void Dijkstra()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    pq.push({0, 1});
    dist[1] = 0;
    
    while(!pq.empty())
    {
        auto [cost, cur] = pq.top();
        pq.pop();
        
        for(int i=0; i<v[cur].size(); i++)
        {
            auto [next, ncost] = v[cur][i];
            
            if(dist[next] > cost + ncost)
            {
                dist[next] = cost + ncost;
                pq.push({dist[next], next});
            }
        }
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    dist.resize(N+1, 500001);
    
    for(int i=0; i<road.size(); i++)
    {
        int n1 = road[i][0];
        int n2 = road[i][1];
        int cost = road[i][2];
        
        v[n1].push_back({n2, cost});
        v[n2].push_back({n1, cost});
    }
    
    Dijkstra();
    
    for(int i=1; i<=N; i++)
    {
        if(dist[i] <= K) answer++;
    }
    return answer;
}

 

다익스트라 알고리즘을 통해 간단히 풀이가 가능한 문제이다.

먼저 두 마을의 번호와 해당 마을을 있는 거리에 따라 초기 값을 설정해준다.

v[n1].push_back({n2, cost});
v[n2].push_back({n1, cost});

마을 n1에 대한 다음 마을(n2)과 비용 저장
마을 n2에 대한 다음 마을(n1)과 비용 저장

 

이후에는 다익스트라 알고리즘을 돌린 후에,

비용이 담긴 dist 배열의 값 중에서 K보다 작거나 같은 케이스만 카운팅하여 반환해주면 된다.