[C++/프로그래머스] 배달

문제 링크

배달

 

풀이

다익스트라로 푸는 문제인데 최소신장트리로 헷갈려서 약간 돌아갔다.

1. 입력받은 road를 이용해 인접리스트를 만들어준다.
2. 거리가 갱신될 dist는 최댓값으로 초기화해준다.
3. 우선순위 큐로 최단 거리를 갱신해준다.
   1. 거리 순으로 정렬 되도록 pair를 {cost, end} 형태로 만들어준다. 그리고 오름차순 정렬한다.
   2. dist[next]>dist[cur]+nextCost라면 거리가 갱신된다는 것이므로 갱신해준 뒤 pq에 push한다.
4. 그렇게 만들어진 dist를 돌면서 k보다 작거나 같다면 1 더해준다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 20000001
using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    vector<vector<pair<int,int>>> arr(N+1);
    for(int i=0;i<road.size();i++) // 인접 리스트 생성
    {
        int stt = road[i][0];
        int end = road[i][1];
        int cost = road[i][2];
        arr[stt].push_back({cost, end});
        arr[end].push_back({cost, stt});
    }

    vector<int> dist(N+1, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    dist[1] = 0;
    pq.push({0, 1}); // 1번 노드부터 시작

    while(!pq.empty())
    {
        int cur = pq.top().second;
        pq.pop();
        for(int i=0;i<arr[cur].size();i++) 
        {
            int next = arr[cur][i].second;
            int nextCost = arr[cur][i].first;
            if(dist[next] > dist[cur]+nextCost) // 거리가 최단으로 갱신되면
            {
                dist[next] = dist[cur]+nextCost;
                pq.push({nextCost, next});
            }   
        }
    }

    for(int i=1;i<dist.size();i++)
    {
        if(dist[i]<=K)
        {
            answer++;
        }
    }

    return answer;
}