Programmers 12978 배달

25 Apr 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12978

나의 풀이

1번 마을에서부터 다른 마을까지의 최단거리를 구하는 문제이기 때문에 dijkstra로 문제를 해결할 수 있다.
1번 마을에서 다른 마을까지의 거리들 중 K이하인 마을의 개수를 구하여 return 한다.

풀이 코드 : 12978 배달

#include <iostream>
#include <vector>
#include <queue>

#define INF 2000000000

using namespace std;


vector<vector<pair<int,int>>> graph;
int dijkstra(int N, int K){
    vector<int> distance(N, INF);
    vector<int> visit;
    visit.resize(N);
    priority_queue<pair<int, int>> pq;
    distance[0] = 0;
    pq.push(make_pair(0,0));
    while(!pq.empty()){
        int curr = pq.top().second;
        int w = pq.top().first;
        pq.pop();
        if(w > distance[curr]) continue;
        if(visit[curr] == 1) continue;
        visit[curr] = 1;
        for(int i=0;i<graph[curr].size();i++){
            int next = graph[curr][i].second;
            int new_w = graph[curr][i].first;
            if(visit[next] != 1 && distance[next] > distance[curr] + new_w){
                distance[next] = distance[curr] + new_w;
                pq.push(make_pair(-distance[next], next));
            }
        }
    }
    int answer = 0;
    for(int i=0;i<N;i++){
        if(distance[i] <= K) answer++; 
    }
    return answer;
}

int solution(int N, vector<vector<int> > road, int K) {
    vector<int> map;
    graph.resize(N);
    for(int i=0;i<road.size();i++){
        int first = road[i][0] - 1;
        int second = road[i][1] - 1;
        int w = road[i][2];
        graph[first].push_back(make_pair(w,second));
        graph[second].push_back(make_pair(w,first));
    }
    int answer;
    answer = dijkstra(N, K);
    
    
    return answer;
}

채점결과