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

문제

 

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

프로그래머스

문제풀이

 

다익스트라 문제이다.

시작마을은 1번 마을이며, 마을 개수에는 1번 마을도 포함시켜야 한다.

2차원 벡터에 pair<int, int>을 집어넣어 roads [마을 1] = {마을 2, 거리}의 형태로 나타낸다.

문제에서 주어진 road를 탐색하면서 roads에 위의 형태로 값을 입력한다.

양방향 간선이므로 roads[마을 1] = {마을 2, 거리}, roads[마을 2] = {마을 1, 거리}의 두 값을 입력한다.

 

다익스트라는 우선순위 큐를 사용하여 마을 1에서의 해당 마을까지의 거리가 최소가 되도록 값을 경신하면 된다.

 

코드

#include <queue>
#include <vector>
#define pii pair<int, int>
#define INF 1e6
using namespace std;

int Dijkstra(int N, int K, vector<vector<pii>>roads) {
    priority_queue<pii>pq;
    pq.push({ 0,1 });
    vector<int>dists(N + 1, INF);
    dists[1] = 0;

    while (!pq.empty()) {
        int dist = -pq.top().first;
        int node = pq.top().second;
        pq.pop();

        for (int idx = 0; idx < roads[node].size(); ++idx) {
            int next_node = roads[node][idx].first;
            int next_dist = roads[node][idx].second;
            if (dists[next_node] > dist + next_dist) {
                dists[next_node] = dist + next_dist;
                pq.push({ -dists[next_node], next_node });
            }
        }
    }
    int ret(0);
    for (int node = 1; node <= N; ++node) {
        if (dists[node] <= K) ++ret;
    }

    return ret;
}

int solution(int N, vector<vector<int>> road, int K) {
    int answer(0);
    vector<vector<pii>>roads(N + 1);
    for (int idx = 0; idx < road.size(); ++idx) {
        int node1 = road[idx][0];
        int node2 = road[idx][1];
        int dist = road[idx][2];

        roads[node1].push_back({ node2, dist });
        roads[node2].push_back({ node1, dist });
    }

    answer = Dijkstra(N, K, roads);

    return answer;
}