[Programmers/C++] 등산코스 정하기

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

프로그래머스

 

문제 분석

XX산의 지점은 출입구, 쉼터, 산봉우리로 나뉘어 있습니다. 우리는 출입구에서 시작해 산봉우리를 한 번만 방문하고 다시 출입구로 돌아오는 등산코스를 찾고자 합니다. 이 코스의 intensity는 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 의미하며, 이를 최소화하는 것이 문제의 핵심입니다.

이 문제는 여러 지점과 등산로가 주어졌을 때, 주어진 조건을 만족하는 최소 intensity 코스를 찾아야 하는 전형적인 그래프 탐색 문제입니다.

문제 해결 접근법

이 문제는 그래프 이론을 적용해 해결할 수 있습니다. 등산로는 양방향으로 연결되어 있기 때문에 무방향 그래프를 다룰 수 있으며, 특정 출입구에서 출발해 산봉우리까지의 경로 중 intensity가 최소가 되는 코스를 찾아야 합니다.

핵심 알고리즘

문제에서 요구하는 조건에 맞춰 다익스트라 알고리즘(Dijkstra's Algorithm)을 활용하여 최단 경로를 구하는 방법을 적용할 수 있습니다. 다익스트라 알고리즘은 특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘으로, 이 문제에서 각 출입구에서 산봉우리까지 가는 경로의 intensity를 최소화하는 데 적합합니다.

1. 그래프 모델링: 지점을 노드, 등산로를 간선으로 간주하여 무방향 그래프를 생성합니다. 각 간선은 이동 시간을 의미합니다.
2. 다익스트라 알고리즘 적용: 출입구에서 출발해 산봉우리까지의 경로 중 최대 이동 시간이 가장 작은 경로를 찾습니다. 이때, 다익스트라 알고리즘을 변형하여, 경로의 최대 이동 시간을 계산합니다.
3. 산봉우리 선택: intensity가 최소가 되는 산봉우리를 찾되, 동일한 intensity일 경우 번호가 작은 산봉우리를 선택합니다.

즉, dist[i] 는 i번째 노드까지의 intensity가 최소가 될 수 있는 최대 intensity 가 기록됩니다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/*
 * n 개의 지점
 * 각 지점은 출입구, 쉼터, 봉우리 중 하나
 * 양방향 통행
 * 휴식없이 이동해야 하는 시간중 가장 긴 시간은 intensity
 * intensity 가 최소가 되는 등산코스
 * 출입구중 한 곳에서 출발
 * 산봉우리는 한번만 방문할 수 있다
 */

unordered_set<int> summit_set;
unordered_set<int> gate_set;
vector<vector<pair<int,int>>> graph;
vector<int> dijkstra(vector<int>& gates, int n){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    vector<int> dist(n+1, INT_MAX);

    for(auto g : gates){
        q.push({0, g});
        dist[g] = 0;
    }

    while(!q.empty()){
        int node = q.top().second;
        int cost = q.top().first;
        q.pop();
        if(summit_set.find(node) != summit_set.end()) continue;

        for(auto g : graph[node]){
            int nNode = g.first;
            int nCost = g.second;
            int intensity = max(cost, nCost);
            if(dist[nNode] > intensity){
                dist[nNode] = intensity;
                q.push({intensity, nNode});
            }
        }
    }
    return dist;
}
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer(2, INT_MAX);
    graph.resize(n + 1);

    for(auto g : gates) gate_set.insert(g);
    for(auto s : summits) summit_set.insert(s);
    for(auto p : paths){
        int a = p[0], b = p[1], c = p[2];
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }

    vector<int> intensity_vector = dijkstra(gates, n);
    std::sort(summits.begin(), summits.end());

    for(auto s : summits){
        if(intensity_vector[s] < answer[1]){
            answer[0] = s;
            answer[1] = intensity_vector[s];
        }
    }

    return answer;
}