[ALGORITHM] LEVEL3 2022 KAKAO TECH INTERNSHIP - 등산코스 정하기

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

프로그래머스

생각의 흐름

1. 최단 길이? 다익스트라를 사용하자
2. paths를 vector배열로 변경
3. 산봉우리에서 다른 곳으로 가면 안되니까 peaks에 산봉우리는 저장하여 priority queue에 넣어줄때 peaks에 체크가 되어있으면 안넣고 진행
4. 시작점을 굳이 하나로 정할 이유가 있을까?
5. gates모두가 시작점이 될 수있고 목적지는 summits 전체이므로 시작점에 gates 값들을 전부 집어넣자!
6. 최소 값만 구하면 되니까 정렬 보다는 단순 최대 값을 꺼내 오는걸로 하자

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<pair<int, int> > ways[50001];
bool peaks[50001];
int dist[50001];

void init(vector<vector<int>> paths, vector<int> summits){
    for(int i=0, sz=paths.size();i<sz;++i){
        int a = paths[i][0];
        int b = paths[i][1];
        int cost = paths[i][2];
        
        ways[a].push_back({b,cost});
        ways[b].push_back({a,cost});
    }
    
    fill(&peaks[0],&peaks[50001],false);
    for(int i=0, sz=summits.size();i<sz;++i){
        peaks[summits[i]]=true;
    }
    
    fill(&dist[0],&dist[50001],987654321);
}

vector<int> calc(int n, vector<int> gates){
    priority_queue<pair<int, int> > pq;
    
    for(int i=0, sz=gates.size();i<sz;++i){
        pq.push({0,gates[i]});
        dist[gates[i]] = 0;
    }
    
    while(!pq.empty()){
        int st=pq.top().second;
        int cost=-pq.top().first;
        
        pq.pop();
        
        if(dist[st]<cost)
            continue;
        
        for(int i=0, sz=ways[st].size();i<sz;++i){
            int next = ways[st][i].first;
            int ncost = ways[st][i].second>cost?ways[st][i].second:cost;
            
            if(dist[next] <= ncost)
                continue;
            
            dist[next] = ncost;
            
            if(!peaks[next])
                pq.push({-ncost,next});
        }
    }
    
    vector<int> answer;
    int gate=0;
    for(int i=0;i<=n;++i){
        if(peaks[i]&&dist[i]<dist[gate])
            gate=i;
    }
    
    answer.push_back(gate);
    answer.push_back(dist[gate]);
    return answer;
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    
    init(paths, summits);
    answer=calc(n, gates);
    
    return answer;
}

결과