프로그래머스 - 등산코스 정하기

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

프로그래머스

 이 문제는 다익스트라 알고리즘을 응용하여 풀 수 있는 문제이다. 흔히 다익스트라 알고리즘은 특정 노드에서 각 노드까지의 최소 거리를 구할 때 이용하는데, 이 문제에서는 거리를 비교하는 부분을 문제에 맞게 살짝 수정하면 되는 문제이다. 그리고 문제에 대한 답이 나올 수 있는 경로는 산봉우리를 기준으로 대칭일 것이다. 왜냐하면 출발, 도착 게이트가 같으며 산봉우리는 경로에 하나만 포함해야 하기 때문에, 게이트 -> 산봉우리에서 최소 intensity가 나온다면, 돌아가는 길 역시 똑같이 돌아가면 되기 때문이다.

3번 예제

 그리고 이를 위해 신경써야 할 부분이 하나 있다. 그것은 바로 산봉우리에서 춟발하는 경로는 계산하지 않는 것이다. 문제의 3번 예제의 답은 5번 산봉우리에 intensity는 1이다. 그런데, 만약 산봉우리에서 춟발하는 경로까지 포함한다면 아래의 이미지와 같은 이유로 답은 변하게 될 것이다. 

만약 산봉우리부터 출발하는 경로까지 포함해서 계산한다면, 아마도 경로는 7 -> 6 -> 5 -> 4 -> 1 -> 4 -> 5 -> 6 -> 7이 될 것이다. 하지만, 이는 문제의 조건에 맞지 않다. 산봉우리는 한 번만 거쳐야 한다. 그렇기 때문에, 이를 신경써서 계산을 해야 한다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 50011
#define INF 987654321

bool isGate[MAX];
bool isSummit[MAX];
int intensity[MAX];
vector<pair<int, int>> links[MAX];

void Check(vector<int> gates)
{
	priority_queue<pair<int, int>> pq;

	for (int i = 0; i < MAX; ++i)
		intensity[i] = INF;

	for (int g = 0; g < gates.size(); ++g)
	{
		int gate = gates[g];

		intensity[gate] = 0;
		pq.push({ gate, 0 });
	}

	while (!pq.empty())
	{
		int curNode = pq.top().first;
		int curIntensity = -pq.top().second;
		pq.pop();

		if (intensity[curNode] < curIntensity)
			continue;

		for (int i = 0; i < links[curNode].size(); ++i)
		{
			int nxtNode = links[curNode][i].first;
			int nxtIntensity = links[curNode][i].second;
			if (0 < curIntensity && nxtIntensity < curIntensity)
				nxtIntensity = curIntensity;

			if (intensity[nxtNode] > nxtIntensity)
			{
				intensity[nxtNode] = nxtIntensity;
				pq.push({ nxtNode, -nxtIntensity });
			}
		}
	}
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits)
{
	vector<int> answer(2, INF);
    
    sort(gates.begin(), gates.end());
    sort(summits.begin(), summits.end());

	for (int i = 0; i < MAX; ++i)
	{
		isGate[i] = false;
		isSummit[i] = false;
		links[i].clear();
	}

	for (int g = 0; g < gates.size(); ++g)
		isGate[gates[g]] = true;

	for (int s = 0; s < summits.size(); ++s)
		isSummit[summits[s]] = true;

	for (int i = 0; i < paths.size(); ++i)
	{
		vector<int> path = paths[i];

		int node1 = path[0];
		int node2 = path[1];
		int dist = path[2];

		links[node1].push_back({ node2, dist });
		links[node2].push_back({ node1, dist });

		if (isGate[node1] == true || isSummit[node2] == true)
			links[node2].pop_back();

		if (isGate[node2] == true || isSummit[node1] == true)
			links[node1].pop_back();
	}

	Check(gates);

	for (int s = 0; s < summits.size(); ++s)
	{
		int summit = summits[s];
		
		if (answer[1] > intensity[summit])
		{
			answer[0] = summit;
			answer[1] = intensity[summit];
		}
	}
	

	return answer;
}