Programers 배달

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

프로그래머스 배달 문제입니다.

 

아이디어

조건에 맞는 거리 중 배달을 갈 수 있는 마을을 찾는 문제입니다.

다익스트라 알고리즘으로 현재 위치에서 배달 할 수 있는 마을의 거리를 계산 후 조건에 맞는 마을들을 찾아내면 되는 문제입니다. 문제가 어렵다면 다익스트라 알고리즘에 대해 공부해볼 필요가 있는 문제입니다.

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
	int answer = 0;
	vector<vector<pair<int, int>>> adj(N + 1);
	vector<int> dist(N + 1, 987654321);
	priority_queue<pair<int, int> > q;
	for (auto iter : road) {
		adj[iter[0]].push_back({ iter[1],iter[2] });
		adj[iter[1]].push_back({ iter[0],iter[2] });
	}
	q.push({ 0,1 });
	dist[1] = 0;

	//우선큐를 이용한 다익스트라로 간선 정리
	while (!q.empty()) {
		int current_dist = -q.top().first;
		int current = q.top().second;
		q.pop();
		if (current_dist > dist[current]) continue;

		for (int i = 0; i < adj[current].size(); i++) {
			int next = adj[current][i].first;
			int next_dist = adj[current][i].second;

			if (dist[next] > next_dist + current_dist) {
				dist[next] = next_dist + current_dist;
				q.push({ -dist[next],next });
			}

		}
	}

	for (auto iter : dist)
		if (iter <= K) answer++;



	return answer;
}