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

[문제]

 

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

프로그래머스

[풀이]

 

해당 문제는 하나의 정점에서 다른 정점들까지의 최단거리를 구하는 문제이므로 다익스트라 알고리즘을 사용해 풀었다.

map이라는 벡터 배열을 선언하여 각 정점마다 인접한 정점까지의 거리를 가지고 있도로 했다.

또한 1번 정점부터 다른 정점들까지의 거리를 구하기 저장하기 위해 dist 변수를 선언하고 정점의 개수만큼 1e9로 초

기화했다.

 

다음으로 dijkstra 함수에서는 priority_queue를 사용해 1번 정점에서 다른 정점들까지의 최단거리를 구하도록 했다.

priority_queue는 {1번 정점에서 해당 정점까지의 최단 거리, 정점}을 pair로 가지도록 되어있고 시작점은 1번 정점이므로 먼저 {0,1}을 queue에 push 해줬다. 

다음으로 queue에서 top에 있는 정점을 뽑아 해당 정점과 인접한 정점들은 방문하고 해당 정점까지의 최단거리를 update 해주면 queue에 push 해준다. 이 때 queue는 거리를 기준으로 오름차순하여 정렬하기 때문에 최단거리를 구할 수 있다. 이러한 방식으로 queue가 empty가 아닐 때까지 반복하여 1번 정점으로부터 각 정점까지의 최단거리를 구하게 된다.

 

마지막으로 각 정점까지의 최단거리가 저장된 dist 배열에서 배달 가능 시간이 K보다 작거나 같은 정점들의 개수를 count 하여 return 해주면 된다. 

 

 

[코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX 51

using namespace std;

vector<int> dist;
vector<pair<int,int>> map[MAX];

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()) {
        int cost = pq.top().first;
        int from = pq.top().second;
        pq.pop();
        for(int i =0 ; i< map[from].size(); i++) {
            int to = map[from][i].first;
            int distance = map[from][i].second + cost;
            if (dist[to] > distance){
                dist[to] = distance;
                pq.push({distance, to});
            }
        }
    }
}

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

    for(int i=0;i<road.size();i++){
        int start = road[i][0];
        int end = road[i][1];
        int cost = road[i][2];
        
        map[start].push_back({end,cost});
        map[end].push_back({start,cost});
        
    }
    
    dist.resize(N+1,1e9);
    dijkstra();
    for(int i=1;i<=N;i++){
        if ( dist[i] <= K)  answer++;
    }
    
    return answer;
}