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

https://school.programmers.co.kr/learn/courses/30/lessons/118669?language=cpp 

프로그래머스

다익스트라의 업그레이드 + 업그레이드 ver.이다.

 

1. 비교 기준이 거리가 아니다.

비교기준은 intensity로, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간이다.

이를 자세히 보는 것을 놓쳤다가 시간이 오래걸렸다..ㅠ

 

2. 산봉우리를 올라가는 경로/ 내려가는 경로를 둘 다 구할 필요는 없다.

 

3. 출발점과 도착점이 여러 개이다.

출발점과 도착점을 각각 하나씩 골라서 다익스트라를 수행했는데, 이렇게 풀면 시간초과가 발생한다.

그런데 굳이 이렇게 풀 필요가 없었다.

다익스트라 알고리즘의 경우 일대다 정점 간 거리를 파악하는 것으로, 출발점이 원래는 하나여야 하는데 이에 대한 구분이 필요없다.

어차피 처음 시작할 때 출발점을 방문한 후, 그 이후에 모든 출발점에 가면 안되기 때문이다. 그래서 아예 방문을 배체하면 된다.

Queue에 모든 출발점에 거리가 0이라는 초기화된 값을 넣어준다.

그리고 Queue에서 pop한 점이 이동 시에 출발점으로 가는 경우를 모두 제거한다.

 

산봉우리는 어떻게 처리하면 될까?

산봉우리는 값은 갱신하되, 다른 점으로 이동하는 경우는 제거하기 위해 Queue에 push하지 않는다.

 

4. Priority Queue가 아닌 Queue를 쓴다.

Priority Queue에는 원소를 삽입을 할 때마다 logN이라는 시간복잡도를 통해 추가적인 정렬이 발생하기 때문에 Queue를 사용해 소요 시간을 최소화한다. 원래는 갱신하는 시간을 최소화하기 위해 일부러 PQ를 쓴 것이었는데, 여기서는 정렬에 더 많은 시간이 소요되는 것 같다.

 

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

vector<pair<int,int>> go(int n, set<int> &gates, set<int> &summits, vector<vector<pair<int,int>>> &edges) {
    queue<pair<int,int>> q;
    vector<pair<int,int>> answers;
    vector<int> dist(n + 1, 1e9);
    for(auto g: gates) {
        q.push({0, g});
        dist[g] = 0;
    }
    
    while(!q.empty()) {
        auto cur = q.front();
        int d = cur.first;
        int pos = cur.second;
        q.pop();
        
        for(int i = 0;i < edges[pos].size();i++) {
            int next = edges[pos][i].first;
            int part_d = edges[pos][i].second;
            // 출입구는 하나만
            if(gates.find(next) != gates.end()) continue;
            
            if(dist[next] > max(dist[pos], part_d)) {
                dist[next] = max(dist[pos], part_d);
                // 산봉우리에서 다른 곳으로 방문 불가
                if(summits.find(next) != summits.end()) continue;
                q.push({dist[next], next});
            }
        }
    }
    
    for(auto summit : summits) {
        int intensity = dist[summit];
        answers.push_back({intensity, summit});
    }
    return answers;
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    vector<vector<pair<int,int>>> edges(n + 1);
    set<int> summits_set(summits.begin(), summits.end());
    set<int> gates_set(gates.begin(), gates.end());
    
    for(auto path : paths) {
        int i = path[0];
        int j = path[1];
        int w = path[2];
        
        edges[i].push_back({j, w});
        edges[j].push_back({i, w});
    
    }
    vector<pair<int,int>> answers = go(n, gates_set, summits_set, edges);
    
    sort(answers.begin(), answers.end());
    
    answer.push_back(answers[0].second);
    answer.push_back(answers[0].first);
    return answer;
}