프로그래머스 - 배달 (Lv.2)

문제 링크

• 👉 배달

문제 설명

• N개의 마을과 각 마을이 양방향으로 통행할 수 있는 도로와 도로를 지날 때 걸리는 시간이 주어진다.
  • N개의 정점과 각 정점을 잇는 간선, 간선의 가중치가 주어진다.
• 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 한다. 1번 마을에서 N개의 마을로 배달할 때 K 시간 이하로 배달이 가능한 마을의 개수를 반환하라.

문제 접근

• 다익스트라 알고리즘
  • 음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘
• 인접리스트의 형태로 마을 간의 연결 정보와 이동하는데 걸리는 시간을 담아둔다.
• 처음 모든 노드로의 최단 거리는 INF 로 설정한다.
  • dist[1] ~ dist[N] 의 초깃값은 INF
• 시작점의 최단 거리는 0이다.
  • 본 문제에서 start는 1번이므로 dist[1] = 0
• 우선순위 큐로 다른 마을로 이동하는데 걸리는 시간에 따른 최소 힙 형태로 마을을 방문하도록 한다.
• 새롭게 방문한 마을까지의 소요 시간이 기존에 얻었던 결과보다 작다면, 우선순위 큐에 넣고 탐색을 계속 진행한다.

구현(All Pass)

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>

#define INF 9e8
using namespace std;

// c = table[u].first, v = table[u].second
// u->v 로 가는 비용 c를 표현
vector<pair<int, int>> table[51]; 
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int dist[51];

void dijkstra(int start){
    dist[start]=0;
    pq.push(make_pair(0, start));
    
    while(!pq.empty()){
        int u = pq.top().second;
        int c = pq.top().first;
        pq.pop();
        
        for(int i=0; i<table[u].size(); i++){
            int v = table[u][i].second;
            int x = table[u][i].first;
            if(dist[v] > c+x){
                dist[v] = c+x;
                pq.push(make_pair(c+x,v));
            }
        }
    }
    
}


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

    for(int i=0; i<road.size(); i++){
        int from = road[i][0];
        int to = road[i][1];
        int cost = road[i][2];
        table[from].push_back(make_pair(cost, to));
        table[to].push_back(make_pair(cost, from));
    }  
    memset(dist, 0, sizeof(dist));
    for(int i=1; i<=N; i++){
        dist[i] = INF;
    }
    dijkstra(1);
    for(int i=1; i<=N; i++){
        // cout << dist[i] << " ";
        if(dist[i]<=K) answer++;
    }
    
    return answer;
}