등산코스 정하기 (feat. 프로그래머스, 118669번)

등산코스 정하기
https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <string>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
set<pair<int, int>> arr[50001];
int ans[50001];
char tmp[50001];
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for (int i = 1; i <= n; ++i)
        ans[i] = 100000000, tmp[i] = 0;
    for (auto& gate : gates)
        tmp[gate] = 'g';
    for (auto& summit : summits)
        tmp[summit] = 's';
    for (auto& path : paths)
        if (tmp[path[0]] == 'g' || tmp[path[1]] == 's')       // 시작점이 입구거나 도착점이 산봉우리인 경우
            arr[path[0]].insert(make_pair(path[1], path[2]));
        else if (tmp[path[0]] == 's' || tmp[path[1]] == 'g')  // 시작점이 산봉우리거나 도착점이 입구인 경우
            arr[path[1]].insert(make_pair(path[0], path[2]));
        else
            arr[path[0]].insert(make_pair(path[1], path[2])), arr[path[1]].insert(make_pair(path[0], path[2]));

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;    // pair<소요시간,정점>
    for (auto& gate : gates)
        q.push(make_pair(0, gate)), ans[gate] = 0;
    while (!q.empty()) {
        auto p = q.top(); q.pop();
        auto x = p.second, t1 = p.first;
        if (ans[x] < t1)
            continue;
        for (auto& temp : arr[x]) {
            auto y = temp.first, t2 = temp.second;
            if (ans[y] > max(t1, t2))
                ans[y] = max(t1, t2), q.push(make_pair(ans[y], y));
        }
    }

    sort(summits.begin(), summits.end());       // 산봉우리 입력값이 정렬되어 있지 않음.. ㅂㄷㅂㄷ
    vector<int> answer{0, 100000000};
    for (auto& sm : summits)
        if (ans[sm] < answer[1])
            answer[0] = sm, answer[1] = ans[sm];
    return answer;
}
// *&)*@*

 

1. 한 지점 (노드, 정점) 은 다른 지점 (출입구, 쉼터, 산봉우리) 으로부터 방문되어질 수 있습니다.
2. 이때 방문한 최대 시간을 기록합니다. (A->B->C로 이동한다고 했을때, C지점의 시간 정보는 A->B로 이동했던 시간과 B->C로 이동했던 시간 중 더 큰 시간을 저장합니다.)
3. 이러한 과정을 거치면 모든 지점은 자신에게 온 다른 지점으로부터의 시간 중 가장 큰 값만 갖게 됩니다.
   (A->B든 C->B든 D->B든 B지점은 그중 가장 큰 시간 정보만 갖게 됩니다.)
4. 따라서 이때 산봉우리 지점의 시간은 출입구로부터 산봉우리까지의 가장 큰 시간 정보를 갖게 됩니다.