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

 

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

 

 

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

다익스트라에 대한 설명은 잘 되어 있는데, 등산코스 문제에 대해서는 초기값을 -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처럼 이미 방문한 노드라면 최단거리에서 걸리기 때문에 큐에 다시 넣을 경우는 없습니다.

 

 

---

 

다시 풀었다. 다익스트라가 맞다.

#include <string>
#include <vector>
#include <queue>
#include <set>
#include <climits>
#define max(a, b) ((a >= b) ? a : b)
using namespace std;
/*
해당 노드를 A출발선에서 먼저 방문했다면, B 출발선에서 나중에 방문해서 갱신할 일이 없음.
그래서 통행료할인같이 안풀어도됨. 누적 거리가 아닌 최대니까.
*/

struct Node {
    int num;
    int distance;
};

vector<Node> nodeVector[50001];
struct PQ {
    int currentNode;
    int currentMax;
    
    bool operator<(const PQ& other) const {
        if(currentMax != other.currentMax) return currentMax > other.currentMax;
        if(currentNode != other.currentNode) return currentNode > other.currentNode;
    }
};
int visit[50001];
bool isSummits[50001];

int N;

set<pair<int, int>> answer;

void bfs(vector<int>& gates) {
    priority_queue<PQ, vector<PQ>> pq;
    
    for(int i = 0; i <= N; i++) {
        visit[i] = INT_MAX;
    }
    
    for(int i = 0; i < gates.size(); i++) {
        pq.push({
            gates[i], 0
        });
        visit[gates[i]] = 0;
    }
        
    while(!pq.empty()) {
        
        auto top = pq.top();
        int currentNode = top.currentNode;
        int currentMax = top.currentMax;
        pq.pop();
        
        if(isSummits[currentNode]) {
            answer.insert({currentMax, currentNode});
            continue;
        }
        
        for(int i = 0; i < nodeVector[currentNode].size(); i++) {
            
            int nextNode = nodeVector[currentNode][i].num;
            int nextDistance = max(currentMax, nodeVector[currentNode][i].distance);
            
            if(visit[nextNode] > nextDistance) {
                pq.push({
                    nextNode, nextDistance
                });
                visit[nextNode] = nextDistance;
            }
        }
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    
    ::N = n;
    // 양방향 연결
    for(int i = 0; i < paths.size(); i++) {
        nodeVector[paths[i][0]].push_back({paths[i][1], paths[i][2]});
        nodeVector[paths[i][1]].push_back({paths[i][0], paths[i][2]});
    }
    
    for(int i = 0; i < summits.size(); i++) {
        isSummits[summits[i]] = true;
    }
    
    bfs(gates);
    
    auto ans = *answer.begin();
    
    return {ans.second, ans.first};
}