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

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define INF 1e18
using namespace std;

vector<vector<int>> node[50001]; // 연결 노드 정보
int dist[50001] = {0,}; //각 노드의 최소 intensity
bool isTop[50001] = {false,}; // 해당 노드가 산봉우리인지
vector<int> ans(2); // 정답

void dijk(vector<int> gates){
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    //모든 출발지점을 큐에 넣기
    for(int i=0; i<gates.size(); i++){
        pq.push({0, gates[i]});
        dist[gates[i]] = 0;
    }
    //시작
    while(!pq.empty()){
        int x = pq.top().second; //현재 노드
        int cost = pq.top().first; // 저장된 intensity
        pq.pop();
        //ans에 값이 있고 최소 intensity가 현재 노드의 intensity보다 작을 때
        if(ans[0] != -1 && ans[1] < cost) continue;
        //해당 노드가 산봉우리일 때
        if(isTop[x]){
            if(ans[0] == -1 || ans[1]>cost){
                ans[0] = x;
                ans[1] = cost;
            }
            //intensity는 같으나 번호가 더 작은 경우 대체
            else if(ans[1] ==cost && ans[0] >x) ans[0] = x;
            continue;
        }
        //연결된 모든 노드 탐색
        for(int i=0; i<node[x].size(); i++){
            int next = node[x][i][0];
            int nCost = node[x][i][1]; //그 노드로 가는 비용
            nCost = max(nCost, cost);
            if(dist[next] ==-1 || nCost<dist[next]){ //dist 배열에 저장된 비용보다 작은 경우
                dist[next] = nCost;
                pq.push({nCost,next});
            }
        }
    }
    
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for (auto it : summits) isTop[it] = true;
    for(int i=0; i<50001; i++){
        dist[i]=-1;
    }
    ans[0] = -1;
    ans[1] = -1;
    for(int i=0; i<paths.size(); i++){
        int n1 = paths[i][0];
        int n2 = paths[i][1];
        int cost = paths[i][2];
        node[n1].push_back({n2,cost});
        node[n2].push_back({n1,cost});
    }
    dijk(gates);
    return ans;
}

<참고>

https://howudong.tistory.com/334

다익스트라 알고리즘의 시간 복잡도는 우선순위큐로 구현했을 때 V*|Elog(V)| 이다.

즉 해당 문제에서 50,000* 200,000*4 = 10^5 * 10^ = 10^10이다. 만약 거의 모든 노드가 출입구라면 시간초과가 난다.

 

해결)

각 노드의 최소 intensity를 저장하는 배열 dist를 만든다.

여기서 이동하는 비용을 합해주지 말고 기존의 비용과 이동하는 새로운 비용 중 더 큰 것으로 갱신해 준다.

모든 출입구에서 다익스트라를 따로 시작하지 말고 어차피 최소 intensity 하나만 구하면 되니까 이를 동시에 실행시키는 것으로 하자

풀이)

x: 지금 도착한 현재 위치(노드 번호)

int next = node[x][i][0]: 다음에 갈 수 있는 노드 번호

int nCost = node[x][i][1]: x → next로 가는 길의 난이도 ex)node[1] = { {2, 5}, {3, 4} }

cost: 지금까지 온 길에서 제일 힘든 구간, nCost: 지금 가려는 길

dist[next]: 지금까지 next로 가는 데 걸린 최소 intensity

pq.push({nCost, next}): 지금 next 노드에 도착했으면, 거기서 또 어디로 갈 수 있는지 봐야 하니까 다음 순서에서 next를 꺼내기 위해 큐에 넣기

 

for (int i = 0; i < paths.size(); i++) {
    int n1 = paths[i][0]; // 시작 지점
    int n2 = paths[i][1]; // 도착 지점
    int cost = paths[i][2]; // 이 경로의 비용(intensity)

} : 입력 받은 등산로(paths) 정보를 그래프(인접 리스트) 형태로 바꾼다.