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

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

프로그래머스

---

문제 설명

n개의 지점이 있는 △산이 있습니다. 각 지점은 1부터 n까지 번호가 붙어 있으며, 입구, 쉼터, 산봉우리 중 하나입니다.

각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 각 등산로마다 이동하는데 일정 시간 intensity가 소요됩니다.

당신은 △산의 출입구 중 한 곳에서 출발해, 산봉우리 중 한 곳만 방문한 뒤 원래의 출입구로 돌아오는 등산코스를 작성하려고 합니다. 즉, 출입구는 처음과 끝 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.

하지만 등산이 너무 힘들기 때문에 한 번 한 번에 지점 사이 이동 시간을 최대한 작게 하려고 합니다. 예를들어 아래 등산 지도에 1, 3번이 입구, 5번이 산봉우리, 나머지가 쉼터라고 할 때 1 → 2 → 4 → 5 → 6 → 4 → 2 → 1과 같이 루트를 짜는게 최대 이동 시간 3이 됩니다.

정보가 주어질 때 조건에 적합한 [산봉우리 번호, intensity 최솟값]을 반환하세요. 만약 intensity가 동일한 산봉우리가 여러개라면 가장 작은 산봉우리를 돌려줘야 합니다.

---

아이디어

● 등산 = 하산
출입구 → ... → 산봉우리 → ... → 출입구에 형태로 등산할 때 등산 소요 시간에 총합이 아니라, 등산을 하며 지나온 간선 에 가장 높은 값을 최소가 되도록 하는 것이고 양방향 간선이기 때문에 출입구 → ... → 산봉우리 까지에 최소 값만 구하면 돌아가는 것은 왔던 루트를 그대로 사용하면 됩니다.

●  가장 빠른 하산

입구를 기반으로 가장 가까운 산봉우리를 선택하면 입구와 산봉우리를 같이 체크해야 하지만, 산봉우리에서 가장 빠른  입구를 찾는 방법은 산봉우리 개수만큼만 체크하면 됩니다. 산봉우리와 입구를 같이 체크시 시간초과.

순회하며 첫 발견하는 입구가 무조건 가장 작은 이동시간을 소요하는 입구이고, 입구에 번호는 중요하지 않기에 입구를 발견시 바로 해당 산봉우리에 순회를 종료하고 다음 산봉우리를 시작하면 됩니다.

---

코드

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

set<int> gateSet, summitSet;
vector<vector<pair<int, int>>> map(50001, vector<pair<int, int>>());
int ansSummit = 0, ansIntensity = 2e9;

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {

    for(auto gate : gates)
        gateSet.insert(gate);
    for(auto summit : summits)
        summitSet.insert(summit);
    for(auto path : paths)
    {
        map[path[0]].push_back({-path[2], path[1]});
        map[path[1]].push_back({-path[2], path[0]});
    }    

    for(auto summit : summits)
    {
        vector<bool> visited(n, false);
        priority_queue<pair<int, int>> pq;

        for(auto s : summits)
            visited[s] = true;

        int intensity = -1;
        for(auto next : map[summit])
            pq.push(next);    

        while(!pq.empty())
        {
            auto current = pq.top(); pq.pop();
            visited[current.second] = true;
            intensity = intensity > -current.first ? intensity : -current.first;

            if(gateSet.find(current.second) != gateSet.end())
            {
                if(intensity == ansIntensity) 
                    ansSummit = ansSummit > summit ? summit : ansSummit;
                else if(ansIntensity > intensity) 
                {
                    ansSummit = summit;
                    ansIntensity = intensity;
                }
                break;
            }

            for(auto next : map[current.second])
            {
                if(visited[next.second]) continue;
                pq.push(next);
            }
        }       
    }
    return {ansSummit, ansIntensity};
}

성능 요약 : 메모리: 5.37 MB, 시간: 0.65 ms

---

피드백

무조건 오타를 조심하고... 왜 안되지 했었는데 우선순위 큐를 초기화를 안해줘서 이전 산봉우리 순회 정보가 남아있는 상태... 초기화 조심