2022 카카오 여름인턴쉽 코딩테스트 4번 등산코스 정하기

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

프로그래머스

아이디어

신경쓸 부분이 상당히 많은 문제이고, 다익스트라 알고리즘을 튜닝하는 것이 핵심 전략으로 느껴집니다.

먼저 출발지에서 봉우리를 찍고 다시 내려올 때 지나갔던 노드를 재방문하는 것이 가능하기 때문에 왔던길을 그대로 내려오면 사실상 출발지 -> 봉우리까지 가는데 intensity가 최소가 되는 방법을 찾으면 됩니다.

다익스트라는 한 점에서 다른 모든 간선까지의 최소 가중치 정보 그래프를 만드는 것이 목표이지만 여기서는 출발지에서 다른 노드까지의 가중치 정보를 변경할때 현재 노드까지의 최대 intensity정보를 입력하는 것으로 튜닝하여야 합니다.

그렇게 되면 모든 시작점에서 모든 봉우리까지의 intensity의 최소값을 찾을 수 있게 됩니다.

주의 할 점은 다음노드가 시작점일때와 시작 노드가 봉우리일때를 처리해줘야 합니다.

다익스트라 알고리즘을 튜닝하여 문제를 풀어본 경험이 처음이라 본인에게 좋은 데이터로 만들기 위해 반복적으로 풀어보는 방법으로 복습을 해야겠네요.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10000001
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int>intensitys;
vector<int>nodeInfo;

enum { GATE = 1, SUMMIT = 2 };

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
	vector<int> answer;
	priority_queue<pair<int, int>> pq;
	adj.resize(n + 1, vector<pair<int, int>>());
	intensitys.resize(n + 1, MAX);
	nodeInfo.resize(n + 1, 0);
	//nodeInfo에 GATE 표시, intensitys 초기화, q에 push
	for (auto& gate : gates) {
		nodeInfo[gate] = GATE;
		intensitys[gate] = 0;
		pq.push({ gate,0 });
	}
	//nodeInfo에 SUMMIT 표시
	for (auto& summit : summits) {
		nodeInfo[summit] = SUMMIT;
	}
	//간선 정보 입력
	for (auto & path : paths) {
		adj[path[0]].push_back({ path[1],path[2] });
		adj[path[1]].push_back({ path[0],path[2] });
	}
	//다익스트라 변형
	while (!pq.empty()) {
		int currentNode = pq.top().first;
		int currentIntensity = pq.top().second;
		pq.pop();

		//SUMMIT일 경우 멈춰야 함
		if (nodeInfo[currentNode] == SUMMIT) continue;

		//현재의 currentIntensity보다 intensitys[currentNode]가 크다면 
		//현재 노드보다 더 작은 intensitys를 가질 수 없기때문에 스킵
		if (intensitys[currentNode] > currentIntensity) continue;

		for (auto& iter : adj[currentNode]) {
			int nextNode = iter.first;
			int nextIntensity = iter.second;

			//GATE로 돌아오면 안됨
			if (nodeInfo[nextNode] == GATE) continue;

			//intensitys[nextNode]를 갱신 할 수 없다면 패스
			if (intensitys[nextNode] <= max(currentIntensity, nextIntensity)) continue;

			//intensitys[nextNode] 업데이트, push in q
			intensitys[nextNode] = max(currentIntensity, nextIntensity);
			pq.push({ nextNode,intensitys[nextNode] });

		}
	}

	//summits을 정렬하여 작은 숫자를 가진 summit가 먼저 처리 되야 함
	sort(summits.begin(), summits.end());
	//최소 intensitys를 찾기 위해 최댓값으로 초기화
	answer = { 0, MAX };
	//intensitys의 최소를 찾자
	for (auto& summit : summits) {
		if (intensitys[summit] >= answer[1]) continue;
		answer[0] = summit;
		answer[1] = intensitys[summit];

	}


	return answer;
}