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

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

프로그래머스

카카오 기출 (다시 풀기)

 

다익스트라 알고리즘이란 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이다.

이를 해당 문제에 적용해본다면 다음과 같이 된다.

 

"한 출입구에서 다른 지점까지의 최소 intensity를 구하기"

 

이때 주의해야할 점은 결국 다익스트라 알고리즘은 최악의 경우 모든 정점을 방문하게 되는데, TLE 발생할 수 있다.

주목해야할 것은 '각 지점은 양방향 통행이 가능한 등산로로 연결'되어 있다는 점이다.

 

즉, 단방향만 생각하면 된다! 한 출입구에서 산봉우리까지의 단방향 최소 intensity를 구했다면, 산봉우리에서 출입구까지의 최소 intensity를 고려하지 않아도 된다는 의미다.

 

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

vector<pair<int, int>> graph[50001];
int isSummits[50001], intensity[50001];

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for(auto p : paths) {
        graph[p[0]].push_back({ p[1], p[2] });
        graph[p[1]].push_back({ p[0], p[2] });
    }
    
    for(auto s : summits) {
        isSummits[s] = 1;
    }
    
    for(int i = 1; i <= n; i++) {
        intensity[i] = -1;
    }
    
    priority_queue<pair<int, int>> pq;
    for(auto g : gates) {
        pq.push({ 0, g });
        intensity[g] = 0;
    }
    
    vector<pair<int, int>> tmp;
    while(!pq.empty()) {
        auto [weight, now] = pq.top();
        pq.pop();
        // cout << weight << " " << now << "\n";
        
        if(intensity[now] < weight) continue;
        
        if(isSummits[now] == 1) {
            tmp.push_back({ intensity[now], now });
            continue;
        }
        
        for(auto g : graph[now]) {
            auto [next, n_weight] = g;
            n_weight = max(weight, n_weight);
            if(intensity[next] == -1 || n_weight < intensity[next]) {
                intensity[next] = n_weight;
                pq.push({ intensity[next], next });
            }
        }
    }
    
    sort(tmp.begin(), tmp.end());
    
    return { tmp[0].second, tmp[0].first };
}