등산코스 정하기 118669

문제

이하생략

접근 방법

문제에서 요구하는 바는 출입구에서 시작하여 산봉우리를 찍고 다시 출입구로 도착하는 것이지만 실질적으로 출입구에서 산봉우리까지의 최소 시간을 구하면 된다. (최소로 도착한 곳을 그대로 왕복하면 되기에 그렇다)

최소 시간을 구하는 법은 다익스트라를 응용하여 각 지점에서의 등산로 시간을 우선순위 큐에 집어넣고 가장 낮은 시간 값을 꺼내오는 식으로 반복하면 된다.

코드

#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits)
{
    vector<int> visted(n + 1, 10000001), type(n + 1);
    vector<vector<pii>> graph(n + 1, vector<pii>());
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    int ret = 10000001, summ;
    for (vector<int> path : paths)
    {
        graph[path[0]].push_back({path[1], path[2]});
        graph[path[1]].push_back({path[0], path[2]});
    }
    for (int gate : gates)
        type[gate] = 1;
    for (int summit : summits)
        type[summit] = 2;
    for (int gate : gates)
    {
        visted[gate] = 1;
        pq.push({1, gate});
    }
    while (!pq.empty())
    {
        pii cur = pq.top();
        int curVal = cur.first, curIdx = cur.second;
        pq.pop();
        if (curVal > ret) // 현재 최솟값보다 큰 경우
            continue;
        for (pii next : graph[curIdx])
        {
            int nextVal = max(curVal, next.second), nextIdx = next.first;
            if (type[nextIdx] == 2)
            {
                if (nextVal == ret)
                    summ = min(summ, nextIdx);
                else if (nextVal < ret)
                {
                    ret = nextVal;
                    summ = nextIdx;
                }
            }
            if (type[nextIdx] || visted[nextIdx] <= nextVal || nextVal > ret) // 출입구인 경우, 이미 낮은 값으로 방문한 경우, 현재 최솟값보다 큰 경우
                continue;
            visted[nextIdx] = nextVal;
            pq.push({nextVal, nextIdx});
        }
    }
    return {summ, ret};
}

풀이

다익스트라를 응용한 문제이다. (다익스트라는 이전 거리를 더하여 이동한다면 지금 문제는 비교하여 높은 값을 가져가는 식이다)

처음에는 백트래킹으로 생각했다. (각 출입구에서 시작하여 산봉우리에 도착하는 경우로 생각했다)
물론 모든 경우를 보면 시간 초과가 분명하기에 안되는 경우는 과감하게 포기하며 가면 된다고 생각했다. (최소가 아닌 경우는 볼 필요가 없다)

코드를 작성하다가 든 생각이 다익스트라로 푸는 것이 해답일 것 같다는 생각이 들었다. 그래도 이미 작성한 코드를 제출해 보기로 했고 제출해 본 결과 예상한 대로 시간 초과가 발생했다.

현재 최솟값보다 큰 경우만 제외하고 같은 경우를 제외하지 않는 이유는 같은 경우이더라도 산봉우리 번호가 더 작은 경우가 있을 수 있기 때문이다. 같으면서 산봉우리 번호가 큰 경우는 산봉우리까지 도착해야 알 수 있기에 제외할 수 없다고 판단했다.