[1일 1알고] 등산코스 정하기

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

프로그래머스

등산코스를 정해야합니다.

 

노드와 간선 사이의 최소거리를 구해야하는데 이 때 최소거리는 해당문제에서 정의가 다릅니다.

사실 거리가 아니라 intensity를 구해야하는데, 이는 출발부터 목적까지의 경로 중 각 노드 간 거리의 최댓값입니다.

 

예를 들어 cost가 3-1-2-5-4 와 같은 경로를 가질 때 intensity는 5인 것이죠

그래서 멀리 돌아가서 총합의 cost가 더 높더라도 intensity가 낮다면 정답이 될 수 있습니다.

---

가장 먼저 생각난 방식은 union-find였습니다. 가장 낮은 cost를 가지는 간선부터 추가해가며, 경로가 이어진다면 이를 정답으로 정하려고 했습니다. 다만 문제점은 출발지 여러개 혹은 정상(summit)여러개를 구분하기가 어렵다는 것이었습니다.

 

따라서 그냥 다익스트라 방식을 약간 변형해서 사용하기로 했습니다.

 

기본적으로 간선에 가중치가 있는 간선을 가지는 트리에서 최솟값을 찾기 위해서는 dist배열을 두고 이를 갱신해나가며 정답을 찾습니다.

 

using namespace std;

// 출입구, 쉼터, 산봉우리
// 등산로 이동 시 일정 시간 소요
// 쉼터 혹은 산봉우리 방문 시 휴식 가능
// 휴식 없이 이동하는 시간 중 가장 긴 시간 = intensity
// intensity최소가 되는 코스
// 산봉우리 중 한 곳을 방문 한 뒤 출입구로 돌아옴
// 출입구 -> 산봉우리 -> 출입구의 형태


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

    vector<vector<pair<int, int>>> graph(n + 1);
    vector<int> dists;

    for (const auto& path : paths)
    {
        int a = path[0];
        int b = path[1];
        int cost = path[2];

        graph[a].push_back({ b, cost });
        graph[b].push_back({ a, cost });
    }

    priority_queue 
        < pair<int, int>, vector<pair<int, int>>, 
        greater<pair<int, int>>> pq;

    dists = vector<int>(n + 1, 1e9);


    vector<bool> isGate(n + 1, false);
    vector<bool> isSummit(n + 1, false);

    for (int gate : gates)
        isGate[gate] = true;

    for (int summit : summits)
        isSummit[summit] = true;

    for (int gate : gates)
    {
        dists[gate] = 0;
        pq.push({ 0, gate });
    }

    int minIntensity = 1e9;
    int minSummit = -1;


    while (!pq.empty())
    {
        auto[curIntensity, cur] = pq.top();
        pq.pop();
        if (curIntensity > dists[cur])
            continue;

        if (isSummit[cur])
            continue;

        for (auto [next, edgeCost] : graph[cur])
        {
            if (isGate[next])
                continue;

            int nextIntensity = max(curIntensity, edgeCost);

            if (nextIntensity < dists[next])
            {
                dists[next] = nextIntensity;
                pq.push({ nextIntensity, next });
            }
        }
    }

    sort(summits.begin(), summits.end());
    for (int summit : summits)
    {
        if (dists[summit] < minIntensity)
        {
            minIntensity = dists[summit];
            minSummit = summit;
        }
    }

    return { minSummit, minIntensity };
}

현재 문제에서 dist는 intensity가 될 것입니다.

 

만약에 현재 탐색노드에서 가지는 intensity가 이전에 해당 노드에 방문했을 때 가지는 최소 intensity보다 크면 다시 탐색할 필요가 없습니다.

 

그리고 해당 위치가 summit이라면 중간 노드로서 활용할 수 없기 때문에 패스합니다.

또한 다음 노드가 gate여도 패스합니다.

 

그리고 다음으로 방문하게 될 노드의 intensity가 dist의 node intensity보다 낮다면 갱신합니다.

 

이를 반복하면 정답이 풀립니다.

 

한가지 방법이 안될 때는 다른 방법을  생각해내는 것도 중요하겠네요