프로그래머스 문제 - 등산코스 정하기

프로그래머스 등산코스 정하기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

출입구, 쉼터, 산봉우리로 이루어진 트리가 주어집니다.
출입구부터 시작하여 쉼터들을 지나 산봉우리에 도달한 후 다시 시작했던 출입구로 돌아가는 등산코스를 만들려고 합니다.
등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.
최소한의 intensity를 가진 등산코스의 산봉우리 번호와 intensity를 순서대로 return해야 합니다.

문제 풀이

출입구에서 노드를 시작하여 산봉우리 노드까지 이동 후 다시 시작했던 출입구 노드까지 이동하며 intensity값들 중의 최소값의 코스를 찾아야합니다.
문제를 잘 읽어보면 올라가면서 갔던 노드들을 내려오면서 다시 갈 수 있으며, 돌아오는 출입구는 시작했던 출입구와 같습니다.
즉, 출입구에서 산봉우리까지 올라간 길을 그대로 내려올 수 있다는 뜻입니다.
그러니 출입구에서 산봉우리까지 올라간 길 중 intensity값의 최솟값을 구하기만 하면 정답을 알아낼 수 있습니다.

일단 간선들을 저장하여 트리를 만들어줍니다.
이때 간선의 가중치들도 같이 저장해줍니다.

vector<pair<int, int>> mountain[50001];
    
//간선 등록
for(vector<int> v : paths)
{
    mountain[v[0]].push_back(make_pair(v[1], v[2]));
    mountain[v[1]].push_back(make_pair(v[0], v[2]));
}

이후 출입구와 산봉우리들이 배열로 주어지지만 한 노드에 도달했을 때 그 노드가 출입구인지 산봉우리인지 알아낼려면 O(n)만큼의 시간복잡도가 일어납니다.
이를 빠르게 알아내기 위해 배열을 사용하여 값을 저장해줍니다. 이를 통해 O(1)의 복잡도를 통해 출입구인지 산봉우리인지 알아낼 수 있습니다.

이후에 시작점과 산봉우리들의 최단 거리를 계산해주면 됩니다.
이때 한 노드에서 모든 노드들 간의 최단거리 계산법인 크루스칼 알고리즘을 이용하면 쉽게 최단거리를 알아낼 수 있습니다.
이후 최단거리들 중 산봉우리에 해당하는 노드의 최단거리를 저장해주며 나머지 시작점들도 똑같이 검색해줍니다.
이후 결과적으로 나온 최소값이 등산코스의 intensity최소값이 됩니다.

//출발점에서 봉우리까지의 최단 거리 탐색
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for(int i = 0; i < gates.size(); i++)
{
    int cur = gates[i];
    q.push(make_pair(0, cur));  //first : intensity, second : 노드 위치
    vector<int> dp(50001, 10000001);    //출발점부터 index까지의 최단 거리 저장
    int visited[50001] = {0,};
    dp[cur] = 0;
    while(!q.empty())
    {
        pair<int, int> curVal = q.top();
        q.pop();
        if(summit[curVal.second] == 1)  //산봉우리일 경우 넘어감
            continue;
        visited[curVal.second] = 1;
        for(pair<int, int> p : mountain[curVal.second])
        {
            if(gate[p.first] == 1)  //출입구일 경우 넘어감
                continue;
            int maxVal = max(curVal.first, p.second);   //intensity 계산
            if(maxVal > result.second)  //만약 intensity가 전 출입구로부터 찾았던 intensity보다 클 경우 넘어감
                 continue;
            if(maxVal < dp[p.first])    //dp에 저장된 값보다 작을 경우 새로 저장 및 경로 탐색
            {
                dp[p.first] = maxVal;
                q.push(make_pair(maxVal, p.first));
            }
        }
    }
    //산봉우리들을 찾아서 intensity의 최소값을 검색 후 저장
    for(int j = 0; j < summits.size(); j++)
    {
        if(dp[summits[j]] < result.second || dp[summits[j]] == result.second && summits[j] < result.first)
        {
            result = make_pair(summits[j], dp[summits[j]]);
        }
    }
}

시간초과를 해결하기 위하여 출입구거나 산봉우리인 경우에는 계산하지 않고 넘어가주었으며, 한 개의 출발점의 계산이 끝난 후 intensity값이 있을 때 나머지 출발점의 최소값을 계산 중 전에 저장해둔 intensity값보다 큰 경우에는 계산을 하지 않고 넘어가주면서 계산량을 크게 줄여주었습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    pair<int, int> result = make_pair(0, 10000001);
    vector<pair<int, int>> mountain[50001];
    int gate[50001] = {0,};
    int summit[50001] = {0,};
    
    //간선 등록
    for(vector<int> v : paths)
    {
        mountain[v[0]].push_back(make_pair(v[1], v[2]));
        mountain[v[1]].push_back(make_pair(v[0], v[2]));
    }
    //출입구와 산봉우리의 빠른 확인을 위해 배열 등록
    for(int val : gates)
    {
        gate[val] = 1;
    }
     for(int val : summits)
    {
        summit[val] = 1;
    }
    
    //출발점에서 봉우리까지의 최단 거리 탐색
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for(int i = 0; i < gates.size(); i++)
    {
        int cur = gates[i];
        q.push(make_pair(0, cur));  //first : intensity, second : 노드 위치
        vector<int> dp(50001, 10000001);    //출발점부터 index까지의 최단 거리 저장
        int visited[50001] = {0,};
        dp[cur] = 0;
        while(!q.empty())
        {
            pair<int, int> curVal = q.top();
            q.pop();
            if(summit[curVal.second] == 1)  //산봉우리일 경우 넘어감
                continue;
            visited[curVal.second] = 1;
            for(pair<int, int> p : mountain[curVal.second])
            {
                if(gate[p.first] == 1)  //출입구일 경우 넘어감
                    continue;
                int maxVal = max(curVal.first, p.second);   //intensity 계산
                if(maxVal > result.second)  //만약 intensity가 전 출입구로부터 찾았던 intensity보다 클 경우 넘어감
                    continue;
                if(maxVal < dp[p.first])    //dp에 저장된 값보다 작을 경우 새로 저장 및 경로 탐색
                {
                    dp[p.first] = maxVal;
                    q.push(make_pair(maxVal, p.first));
                }
            }
        }
        //산봉우리들을 찾아서 intensity의 최소값을 검색 후 저장
        for(int j = 0; j < summits.size(); j++)
        {
            if(dp[summits[j]] < result.second || dp[summits[j]] == result.second && summits[j] < result.first)
            {
                result = make_pair(summits[j], dp[summits[j]]);
            }
        }
    }
    
    answer.push_back(result.first);
    answer.push_back(result.second);
    
    return answer;
}

출저

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