[Programmers] Lv3. 배달

• 이 글은 c++로 풀이를 작성하였습니다.

문제

예시

---

풀이

	#include <iostream>
	#include <vector>
	#include <queue>
	#include <utility>
	#include <iostream>
	using namespace std;
	int INF = 50000001;
	int dist[51];
	int check[51];
	// 다익스트라로 알고리즘 해결
	// 우선순위 큐 정렬, 최소비용 순으로 정렬
	struct cmp{
	bool operator()(pair<int,int> a,pair<int,int> b){
	return a.second>b.second;
	}
	};
	void dijstra(int vec[51][51], int start,int N){
	priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
	// 시작점부터 각 노드까지 거리 초기화
	for(int i=1;i<=N;i++){
	dist[i]=vec[start][i];
	pq.push(make_pair(i,dist[i]));
	}
	// 우선순위 큐에 모두 비어있을 경우, 즉 모든 노드를 다 탐색했을 경우
	while(!pq.empty()){
	int node = pq.top().first;
	pq.pop();
	check[node] = true; // 탐색했는지 확인, 최소 순으로 탐색하기 때문에 탐색되었다는 뜻이 최소 비용 계산 완료
	for(int i=1;i<=N;i++){
	if(!check[i]){
	if(dist[node] + vec[node][i] < dist[i]){ // 기존 거리보다 node 정점을 거쳐서 가는 거리가 작을 경우
	dist[i] = dist[node] + vec[node][i];
	pq.push(make_pair(i,dist[i]));
	}
	}
	}
	}
	}
	int solution(int N, vector<vector<int> > road, int K) {
	int answer = 0;
	int vec[51][51]={0};
	for(int i=1;i<=N;i++){
	for(int j=1;j<=N;j++){
	vec[i][j]= i==j?0:INF;
	}
	}
	for(int i=0;i<road.size();i++){
	int s = road[i][0];
	int e = road[i][1];
	int cost = road[i][2];
	if(cost<vec[s][e]){
	vec[s][e] = cost;
	vec[e][s] = cost;
	}
	}
	dijstra(vec,1,N);
	for(int i=1;i<=N;i++){
	cout<<dist[i]<<' ';
	if(dist[i]<=K){
	answer++;
	}
	}
	return answer;
	}

view raw Programmers Lv3.delivery.cpp hosted with ❤ by GitHub

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.