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

 

이전에 풀었던 적이 있는데, 다익스트라를 복습할 겸 다시 풉니다.

 

 

이전 풀이를 공부한 뒤에 다시 풀었는데, 이전에 풀었던 거에 다소 불필요한 부분이 있어서 풀이를 보고 헷갈렸다.

다익스트라에 대한 설명은 잘 되어 있는데, 등산코스 문제에 대해서는 초기값을 -1로 세팅하고 분기하는 불필요한 과정이 있었습니다.

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

#define MAX(a, b) ((a >= b) ? a:b)

using namespace std;

vector<vector<pair<int, int>>> v(50001, vector<pair<int, int>>());
vector<int> interval(50001, INT_MAX);
vector<pair<int, int>> answer;

void dijkstra(int n, vector<int>& gates, vector<int>& summits) {
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for(const auto& gate: gates) {
        pq.push({0, gate});
        interval[gate] = 0;
    }
    
    while(!pq.empty()) {
        
        int node_interval = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        
        if(find(summits.begin(), summits.end(), node) != summits.end()) {
            answer.push_back({node_interval, node});
            continue;
        }
        
        for(int i = 0; i < v[node].size(); i++) {
            
            int new_interval = v[node][i].second;
            int new_node = v[node][i].first;
            int max_interval = MAX(new_interval, node_interval);

            if(max_interval < interval[new_node]) {
                interval[new_node] = max_interval;
                pq.push({max_interval, new_node});
            }
        }
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    
    for(const auto& path: paths) {
        v[path[0]].push_back({path[1], path[2]}); // 지점, 지점, 길이
        v[path[1]].push_back({path[0], path[2]});
    }
    
    dijkstra(n, gates, summits);
    
    sort(answer.begin(), answer.end());
    
    
    return {answer[0].second, answer[0].first};
}

 

 

기본적인 다익스트라의 원리는

'현재까지 온 값 + 다음 노드까지의 값' 이, distance[다음노드] 보다 작으면(=최단거리라면) 

distance[다음노드] 의 최단거리를 갱신해주고 큐에 push 해주는데

 

등산코스 정하기 문제는

'MAX(현재까지 온 값, 다음노드까지의 값)'이, distnace[다음노드] 보다 작으면(최단거리라면)

distance[다음노드] 의 최단거리를 갱신해주고 큐에 push 해주면 됩니다.

 

다익스트라에서는 visit을 사용하는 대신의 distance를 이용하여 분기처리를 해준다는 특징이 있습니다.

BFS처럼 이미 방문한 노드라면 최단거리에서 걸리기 때문에 큐에 다시 넣을 경우는 없습니다.