[프로그래머스] 배달

[프로그래머스] 배달

문제 링크

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

vector<pair<int, int>> edge[51];
int result[51];
void dijkstra(int start){
    result[start] = 0;
    
    //min_heap -> 거리가 가까운 순서대로 정렬됨
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));

    while(!pq.empty()){
        int here = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        //인접 노드들 탐색
        for(int i=0; i<edge[here].size(); i++){
            int there = edge[here][i].first;
            int dist = edge[here][i].second + cost;

            //최단 경로가 가능하다면 업데이트
            if(dist < result[there]){
                result[there] = dist;
                pq.push({dist, there});
            }
        }
    }
}

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

    for(int i = 1; i <= N; i++){
        result[i] = INF;
    }

    for(int i = 0; i < road.size(); i++){
        edge[road[i][0]].push_back(make_pair(road[i][1], road[i][2]));
        edge[road[i][1]].push_back(make_pair(road[i][0], road[i][2]));
    }

    dijkstra(1);

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

• 다익스트라구나 라고 생각하고 풀었는데 구현을 못해서 답을 봤다..ㅎ
• min heap으로 구현 시 first값을 기준으로 정렬로 알고 있는데, 테스트케이스가 모두 거리가 가까운 순서대로 정렬이 돼 있는지 pq.push(make_pair(인덱스, 거리));로 해도 답이 나온다.
• 데이터 갯수가 더 많거나 시간이 빡빡할 시에는 시간 초과 날 것 같다. 방문 처리로 똑같은 노드를 방문하지 않도록 해야겠다.