등산코스 정하기

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

2023년 11월 30일: 29점

#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

struct Data
{
    int Node, Intensity;
    Data(int Node, int Intensity)
    {
        this->Node = Node;
        this->Intensity = Intensity;
    }
    bool operator<(const Data& b) const
    {
        return Intensity > b.Intensity;
    }
};

vector<pair<int, int>> Graph[50001];
int Check[50001];
int Intensities[50001];

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    map<int, int> Gates, Summits;
    priority_queue<Data> pQ;
    
    for(int i = 0; i < gates.size(); ++i) Gates[gates[i]]++;
    for(int i = 0; i < summits.size(); ++i) Summits[summits[i]]++;
    
    for(int i = 0; i < paths.size(); ++i)
    {
        int Node1 = paths[i][0];
        int Node2 = paths[i][1];
        int Cost = paths[i][2];
        
        // 게이트라면 나가는 경로만, 산봉우리라면 들어오는 경로만 담기.
        if(Gates[Node1]) Graph[Node1].push_back(make_pair(Node2, Cost));
        if(Gates[Node2]) Graph[Node2].push_back(make_pair(Node1, Cost));
        if(Summits[Node1]) Graph[Node2].push_back(make_pair(Node1, Cost));
        if(Summits[Node2]) Graph[Node1].push_back(make_pair(Node2, Cost));
        if(!Gates[Node1] && !Gates[Node2] && !Summits[Node1] && !Summits[Node2])
        {
            Graph[Node1].push_back(make_pair(Node2, Cost));
            Graph[Node2].push_back(make_pair(Node1, Cost));
        }
    }
    
    int MinSummitIndex = 2147000000, MinIntensity = 2147000000;
    
    // 출발지 하나하나에 대해서 다익스트라.
    for(int i = 0; i < gates.size(); ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            Check[j] = 0;
            Intensities[j] = -1;
        }
        
        int Gate = gates[i];
        Check[Gate] = 1;
        Intensities[Gate] = 0;
        pQ.push(Data(Gate, 0));
        
        while(!pQ.empty())
        {
            Data CurData = pQ.top();
            pQ.pop();
            
            Check[CurData.Node] = 1;
            
            for(int j = 0; j < Graph[CurData.Node].size(); ++j)
            {
                int NextNode = Graph[CurData.Node][j].first;
                int NextIntensity = Graph[CurData.Node][j].second;
                
                if(Check[NextNode]) continue;
                
                Intensities[NextNode] = max(NextIntensity, Intensities[CurData.Node]);
                pQ.push(Data(NextNode, Intensities[NextNode]));
            }
        }
        
        /*for(int j = 1; j <= n; ++j)
        {
            printf("%d ", Intensities[j]);
        }
        printf("\n");*/
        
        for(int j = 0; j < summits.size(); ++j)
        {
            if(MinIntensity >= Intensities[summits[j]])
            {
                if(MinIntensity == Intensities[summits[j]])
                {
                    MinSummitIndex = min(MinSummitIndex, summits[j]);
                }
                else MinSummitIndex = summits[j];
                MinIntensity = Intensities[summits[j]];
            }
        }
    }
    
    answer.push_back(MinSummitIndex);
    answer.push_back(MinIntensity);
    
    // 산봉우리의 번호, intensity의 최솟값.
    return answer;
}

---

2023년 11월 30일: 100점

struct Result와 Data의 정렬 방법이 달라 똑같은 멤버를 가지고 있음에도 불구하고 struct를 각각 만든게 마음에 안 든다.

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

using namespace std;

vector<pair<int, int>> Maps[50001];
int Intensities[50001];
bool bSummits[50001];
vector<int> answer;

struct Data
{
    int Node, Cost;
    Data(int Node, int Cost)
    {
        this->Node = Node;
        this->Cost = Cost;
    }
    bool operator<(const Data& b) const
    {
        if(Cost != b.Cost) return Cost > b.Cost;
        if(Node != b.Node) return Node < b.Node;
        return false;
    }
};

struct Result
{
    int Node, Cost;
    Result(int Node, int Cost)
    {
        this->Node = Node;
        this->Cost = Cost;
    }
    bool operator<(const Result& b) const
    {
        if(Cost != b.Cost) return Cost < b.Cost;
        if(Node != b.Node) return Node < b.Node;
        return false;
    }
};

void Dijkstra(const vector<int>& gates)
{
    // 받은 gates를 우선순위 큐에 push.
    priority_queue<Data> pQ;
    for(int i = 0; i < gates.size(); ++i)
    {
        Intensities[gates[i]] = 0;
        pQ.push(Data(gates[i], 0));
    }
    
    vector<Result> Results;
    
    while(!pQ.empty())
    {
        int NowNode = pQ.top().Node;
        int RecordedCost = pQ.top().Cost;
        
        pQ.pop();
        
        if(RecordedCost > Intensities[NowNode]) continue;
        if(bSummits[NowNode] == true)
        {
            Results.push_back(Result(NowNode, RecordedCost));
            continue;
        }
        
        for(int i = 0; i < Maps[NowNode].size(); ++i)
        {
            int NextNode = Maps[NowNode][i].first;
            int NextCost = Maps[NowNode][i].second;
            
            if(Intensities[NextNode] == -1 || max(RecordedCost, NextCost) < Intensities[NextNode])
            {
                Intensities[NextNode] = max(RecordedCost, NextCost);
                pQ.push(Data(NextNode, Intensities[NextNode]));
            }
        }
    }
    
    sort(Results.begin(), Results.end());
    
    /*for(int i = 0; i < Result.size(); ++i)
    {
        printf("%d, %d\n", Result[i].Node, Result[i].Cost);
    }*/
    
    answer.push_back(Results[0].Node);
    answer.push_back(Results[0].Cost);
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for(int i = 0; i < paths.size(); ++i)
    {
        int Node1 = paths[i][0];
        int Node2 = paths[i][1];
        int Cost = paths[i][2];
        Maps[Node1].push_back(make_pair(Node2, Cost));
        Maps[Node2].push_back(make_pair(Node1, Cost));
    }
    
    for(int i = 1; i <= n; ++i) Intensities[i] = -1;
    for(int i = 0; i < summits.size(); ++i) bSummits[summits[i]] = true;
    
    Dijkstra(gates);
    
    return answer;
}