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

등산코스정하기 (프로그래머스 Level 3)

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

조금 특이한 방식의 길찾기 문제이다
문제가 조금 복잡하게 설명되어 있지만
요지는 ‘시작점에서 목적지까지 가는 중, 단일 길의 비용이 적은 것을 고르는 문제’이다
(누적 비용은 고려하지 않는다)

문제에서 유의해야 할 점은
‘등산로 입구’가 처음과 끝의 한 번, ‘산봉우리’는 한 번만 포함
이라는 설명이 있는데
‘등산로 입구’와 ‘산봉우리’를 제외한 나머지 위치는 ‘중복방문’이 허용된다
따라서
‘등산로 입구 -> 산봉우리’의 경로만 신경을 쓰면 되는 길찾기 문제이다
(다만 처음에는 ‘중복 방문’과 ‘단일 길의 비용이 적은 것만을 고려’ 라는 측면에 있어
최단거리 길찾기 보다 DFS를 먼저 떠올려 진행하였다)

처음에는 DFS(백트래킹) + DP 의 조합으로 풀려 하였으나
DFS의 특성상 모든 루트를 탐색하기에 DP를 사용하더라도 여전히 느렸으며,
일부 테스트 케이스를 통과할 수 없었기에
(아마 특정 ‘등산로 입구’에서 먼저 DFS를 돌게 되어 차후 비용 비교에 영향을 준 것으로 추정)

따라서 우선순위 큐를 사용하는 다익스트라를 통하여
가능한 ‘경로의 비용이 낮은’ 노드를 우선하여 탐색하도록 하는 방식으로 풀 수 있었다
(추가적으로 더 좋은 경우의 수가 방문될 수 있으니 목적지에 도착하더라도 바로 break를 하지 않았다)

DFS와 BFS에 대하여 익숙해진 듯 하면서도
이번 문제가 ‘최단 거리’와 관련이 있다고 생각하지 못하여
삽질을 하였다

Code

#include <vector>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<limits.h>
#include<queue>

using namespace std;

struct Edge
{
	int target;
	int cost;
};

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
	vector<int> answer;
	vector<int> dp(n + 1, INT_MAX);
	answer.push_back(INT_MAX);
	answer.push_back(INT_MAX);

	sort(gates.begin(), gates.end());
	sort(summits.begin(), summits.end());

	unordered_map<int, vector<Edge>> m;
	for (const auto& path : paths)
	{
		int start = path[0];
		int end = path[1];
		int cost = path[2];

		if (m.find(start) == m.end())
			m[start] = vector<Edge>();

		m[start].push_back({ end,cost });

		if (m.find(end) == m.end())
			m[end] = vector<Edge>();

		m[end].push_back({ start,cost });
	}

	// 비용 순으로 정렬시키기
	for (auto& p : m)
	{
		sort(p.second.begin(), p.second.end(), [](const Edge& a, const Edge& b) {
			if (a.cost == b.cost)
				return a.target < b.target;
			return a.cost < b.cost;
			});
	}

	unordered_set<int> gs(gates.begin(), gates.end());
	unordered_set<int> ss(summits.begin(), summits.end());

	struct node
	{
		int end, cost;
	};

	struct Compare
	{
		bool operator() (const node& a, const node& b)
		{
			if (a.cost == b.cost)
				return a.end > b.end;

			return a.cost > b.cost;
		}
	};

	priority_queue<node, vector<node>, Compare> pq;

	for (int g : gates)
	{
		dp[g] = 0;
		pq.push({g,0});
	}

	vector<bool> visited(n + 1, false);

	while (pq.empty() == false)
	{
		auto n = pq.top();
		pq.pop();

		// 이미 더 좋은 상황으로 방문됨
		if (n.cost > dp[n.end])
			continue;

		if (visited[n.end] == true)
			continue;

		dp[n.end] = n.cost;
		visited[n.end] = true;

		// 도착
		if (ss.find(n.end) != ss.end())
		{
			if (answer[1] > n.cost || (answer[1] == n.cost && answer[0] > n.end))
			{
				answer[0] = n.end;
				answer[1] = n.cost;
			}

			visited[n.end] = false;
			continue;
		}

		for (const Edge& v : m[n.end])
		{
			int cost = max( n.cost,v.cost);
			pq.push({ v.target,cost });
		}
	}

	return answer;
}