[Programmers] 등산코스 정하기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

다익스트라 알고리즘을 활용하여 풀 수 있는 문제였습니다.

일반적인 다익스트라 알고리즘처럼 가중치를 더해나가는 것이 아니라 등산로 내 최대 가중치를 업데이트하는 방식으로 코드를 작성해야 했습니다.

 

	#include <string>
	#include <vector>
	#include <set>
	#include <queue>
	#include <algorithm>
	#include <functional>
	#include <cstring>
	using namespace std;
	const int MAX = 5e5 + 5;
	int maxDist[MAX];
	bool isSummit[MAX];
	set<pair<int, int>> graph[MAX];
	vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
	for (vector<int> path : paths)
	{
	graph[path[0]].insert({path[2], path[1]});
	graph[path[1]].insert({path[2], path[0]});
	}
	for (int summit : summits)
	{
	isSummit[summit] = true;
	}
	vector<pair<int, int>> v;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	memset(maxDist, -1, sizeof(maxDist));
	for (int gate : gates)
	{
	pq.push({0, gate});
	maxDist[gate] = 0;
	}
	while (!pq.empty())
	{
	int dist = pq.top().first;
	int cur = pq.top().second;
	pq.pop();
	if (dist > maxDist[cur])
	{
	continue;
	}
	if (isSummit[cur])
	{
	v.push_back({dist, cur});
	continue;
	}
	for (pair<int, int> p : graph[cur])
	{
	int nextDist = p.first;
	int next = p.second;
	if (maxDist[next] == -1
	|| maxDist[next] > max(dist, nextDist))
	{
	maxDist[next] = max(dist, nextDist);
	pq.push({maxDist[next], next});
	}
	}
	}
	sort(v.begin(), v.end());
	vector<int> answer;
	answer.push_back(v[0].second);
	answer.push_back(v[0].first);
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~