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

문제 URL

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

프로그래머스

[문제 설명]

다음 문제는 마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을(간선을 통한 이동 시간이 K시간 이하)의 개수를 return 문제이다. 

 

마을과 도로 정보의 예시

 

 

[문제 풀이]

문제는 다익스트라 알고리즘을 사용하여 풀 수 있는 문제였다.

우선순위 큐를 사용하여 현재 노드의 위치값과 이동거리를 삽입해 주고, while문을 통해 현재 위치와 연결된 모든 노드들과 거리를 비교해 준다. 이후 저장한 최소 누적 이동값들 중 K 이하의 개수만큼 answer을 증가시켜 주면 된다.

---

#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int,int>> V[51];  // 마을의 양방향 간선 벡터
vector<int> Dist;  // 각 마을의 최소 거리를 저장해 줄 벡터

void Dijkstra(int N) {
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, 1));
    Dist[1] = 0;
 
    while (pq.empty() == 0) {
        int Cost = -pq.top().first;
        int Cur = pq.top().second;
        pq.pop();
 
        for (int i = 0; i < V[Cur].size(); i++) {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost) {
                Dist[Next] = Cost + nCost;
                pq.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}
 
int solution(int N, vector<vector<int> > road, int K) {
    Dist.resize(N + 1, 1e9);  // 벡터 resizing
    for (int i = 0; i < road.size(); i++) {  // 양방향 간선의 값 모두 저장
        int N1 = road[i][0];
        int N2 = road[i][1];
        int Dist = road[i][2];
 
        V[N1].push_back(make_pair(N2, Dist));
        V[N2].push_back(make_pair(N1, Dist));
    }
 
    Dijkstra(N);
    int answer = 0;
    for (int i = 1; i <= N; i++) {
        if (Dist[i] <= K)
            answer++;
    }
 
    return answer;
}

참고: https://astrid-dm.tistory.com/389