문제 푼 날짜 : 2021-08-12

문제

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

접근 및 풀이

1번 마을에 있는 음식점에서 각 마을로 음식 배달을 해야하는데, 각 마을까지 걸리는 시간을 구해야한다.
곧바로 Dijkstra 알고리즘을 떠올렸고, 일반적인 Dijkstra 알고리즘을 구현한 후에 1번에서 다른 마을까지의 거리(시간)이 K이하인 마을의 수를 구해주었다.

코드

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

using namespace std;

#define INF 987654321

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    
    vector<pair<int, int>> map[51];
    
    for (auto r : road) {
        map[r[0]].push_back(make_pair(r[1], r[2]));
        map[r[1]].push_back(make_pair(r[0], r[2]));
    }
    
    vector<int> dist(51, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    pq.push({ 1, 0 });
    dist[1] = 0;
    
    while (!pq.empty()) {
        int now = pq.top().first;
        int cost = pq.top().second;
        pq.pop();
        
        if (dist[now] < cost) {
            continue;
        }
        for (int i = 0; i < map[now].size(); i++) {
            int next = map[now][i].first;
            int nCost = cost + map[now][i].second;
            
            if (dist[next] > nCost) {
                dist[next] = nCost;
                pq.push({ next, nCost });
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        if (dist[i] <= K) {
            answer++;
        }
    }

    return answer;
}

결과

피드백

Dijkstra 알고리즘 구현도 익숙해지고 있는 것 같다.