등산코스 정하기 [Lv. 3]

프로그래머스

여러개의 등산 코스가 있을 때 각 코스의 휴식 없이 이동해야 하는 시간중 가장 큰 시간을 K라고 할때

각 코스의 K중 가장 작은 것을 찾는 문제입니다.

 

조건 1. 각 등산 코스에서 휴식 없이 이동해야 하는 시간중 가장 큰 시간을 찾자

조건 2. 각 코스의 가장 높은 비용의 간선들 중 가장 작은 비용의 간선을 가진 코스를 선택하자.

 

풀이 방법

모든 경로를 탐색하는 DFS를 사용하여도 풀이가 가능합니다. 다만 시간 초과의 위험이 있기 때문에

각 노드를 한번 씩만 방문하여 해결 할 수 있게 해주는 Dijkstra 알고리즘을 이용하면 됩니다.

 

Dijkstra알고리즘에서 사용하는 우선순위 큐는 가장 낮은 비용의 간선을 우선순위로 배정해줍니다.

때문에 조건 2는 자동으로 해결됩니다.

문제 해결 과정에서 가장 높은 비용을 제외한 모든 비용들은 알 필요가 없습니다.

즉 우선순위 큐에 다음 비용을 넣을 때 현재 간선의 비용과 현재까지의 가장 큰 비용중 더 큰 값을 보내면 됩니다.

 

정답 코드

#include <vector>
#include <queue>

# define INF 10000001
using namespace std;

static vector<bool>visited;
static vector<vector<pair<int,int>>> v;
static bool isTop[50001];

int answer[2] {0, INF};

 

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    v.resize(n + 1);
    visited.resize(n + 1);
    
    for (auto path : paths)
    {
        v[path[0]].push_back(make_pair(path[1], path[2]));
        v[path[1]].push_back(make_pair(path[0], path[2]));
    }
    
    for (int& n : summits)
        isTop[n] = true;
        
    BFS(gates);
   
    return {answer[0], answer[1]};
}

 

void dijkstra(vector<int>& gates)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    
    for(int& n : gates)
        q.push(make_pair(0, n));

    while(!q.empty())
    {
        int node = q.top().second;
        int cost = q.top().first;
        q.pop();
        
        visited[node] = true;
        
        if (cost > answer[1])
            continue;
            
        if (isTop[node])
        {
            if (cost < answer[1])
            {
                answer[0] = node;
                answer[1] = cost;
            }
            else if (node < answer[0])
            {
                answer[0] = node;
            }
            continue;
        }
        
        for (auto p : v[node])
        {
            int next = p.first;
            int nxtCost = p.second;
            if (visited[next])
                continue;
            
            nxtCost = max(p.second, cost);
            q.push(make_pair(nxtCost, next));
            
        }
    }
    
}