[프로그래머스] 배달

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    vector<vector<pair<int, int>>> roadInfo(N+1);
    vector<int> dist(N+1, K+1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for(int i=0; i<road.size(); i++){
        int a = road[i][0];
        int b = road[i][1];
        int c = road[i][2];
        
        roadInfo[a].push_back({b, c});
        roadInfo[b].push_back({a, c});
    }
    
    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();
        
        if (currentDist > dist[currentNode]) {
            continue;
        }

        for (auto next : roadInfo[currentNode]) {
            int nextNode = next.first;
            int nextDist = next.second;

            if (dist[nextNode] > currentDist + nextDist) {
                dist[nextNode] = currentDist + nextDist;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }

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

---

📝 풀이

도로 정보를 a마을에 인접한 마을 정보를 (마을 번호, 거리) 형식으로 저장합니다.

다익스트라 알고리즘을 1번 마을부터 시작합니다.

현재 마을에서 인접한 다른 마을을 확인하며 거쳐서 가는 것이 더 짧다면 정보를 갱신합니다.

모든 도로를 확인하면 반복문은 종료됩니다.

이후 저장된 마을까지의 최단 거리를 K와 비교하여 answer을 증가시킨 후 return 합니다.