Programmers_배달

최단거리 다익스트라 알고리즘을 활용하는 문제였다. 이제 슬슬 다익스트라가 손에 익을 때도 됐는데, 잘 안익네...

• 1번 마을에서 N번 마을까지 cost=K 이하인 마을을 구하면 되는 문제.
• 그냥 아무 응용도 없이 다익스트라만 사용해주면 풀 수 있는 문제.
• dist는 최댓값으로 모두 설정해주고, 각 거리를 다니며 갱신시켜주는 방식.
• 처음에 vertex[road[i][0]].push_back(make_pair(road[i][1], road[i][2])); 만 삽입해줬는데, 안되더라.. 그래서 방향을 바꾸고 삽입을 해줬더니 됐다.

💻 전체 코드

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

using namespace std;

vector<pair<int, int> > vertex[51];
int dist[51];
int answer = 0;

void bfs(int N, int K)
{
    priority_queue<pair<int,int>>q;
    q.push(make_pair(0, 1));
    dist[1]=0;
    
    while(!q.empty())
    {
        int cost = -q.top().first;
        int cur = q.top().second;
        q.pop();
        
        for(int i=0;i<vertex[cur].size();i++)
        {
            int next = vertex[cur][i].first;
            int ncost = vertex[cur][i].second;
            if (dist[next] > cost + ncost)
            {
                dist[next] = cost + ncost;
                q.push(make_pair(-dist[next], next));
            }
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(dist[i]<=K) answer++;
    }
}

int solution(int N, vector<vector<int> > road, int K) {

    for(int i=0;i<road.size();i++)
    {
        vertex[road[i][0]].push_back(make_pair(road[i][1], road[i][2]));                 
        vertex[road[i][1]].push_back(make_pair(road[i][0], road[i][2]));      
    }
    
    for(int i=1;i<=N;i++)
        dist[i] = 987654321;
    
    bfs(N,K);

    return answer;
}