[프로그래머스/C++] 등산코스 정하기 (2022 KAKAO TECH INTERNSHIP)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제에서 핵심은 특정 노드를 방문할 때마다 경로 중에서 가장 시간이 오래걸린 값을 저장해야 된다는 것이다.

 

그리고 가장 시간이 오래 걸리는 구간의 크기가 같다면 봉우리의 숫자가 가장 작은 값을 return해야한다.

 

이와 비슷한 문제를 해결하는 알고리즘 중에는 다익스트라 알고리즘이 있는데, 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘으로 가장 작은 값을 계속해서 계산해 나가는 알고리즘이다.

 

이 문제도 마찬가지로 항상 intensity가 가장 작은 값을 가지고 있으면서 만약 intensity가 같다면 mountain의 번호가 가장 작은 경로를 먼저 계산하면 편하다.

 

여기서 위 그림과 같이 S에서 시작을 한다고 가정을 해보자.

 

그러면 3가지 경로에 대해서 intensity를 계산하고, 새롭게 방문이 가능한 N노드들에 대해 다시 갈 수 있는 경로를 탐색해야 한다.

 

문제는 노드가 추가가 되고, 어떤 노드를 먼저 탐색할지 결정을 하려면 시간이 오래 걸린다.

 

그러므로 노드를 추가하는 시점으로 우선 순위에 따라 정렬을 해 앞에서부터 탐색을 하는 자료구조를 이용하면 쉽다.

 

C++에서 사용할 수 있는 자료구조 중에는 pq, multiset, set이 있다. 

 

pq나 multiset은 중복을 허용하기 때문에 이 문제에 좀 더 적합하다고 생각한 set 자료구조를 사용했다.

 

set에서 우선순위로 정렬을 했으므로, 항상 set의 맨 앞 노드를 가져와서 새로운 노드들을 방문하면 된다.

 

그리고 조건 중에 intensity가 같으면 봉우리의 숫자가 작은 곳을 return하기로 했으므로, 봉우리 정렬해 봉우리의 숫자가 작은 곳부터 출발지에 도착할 수 있는지 탐색을 하면 된다.

 

이렇게 할 경우 봉우리가 큰 상태에서 특정 노드를 방문했을 때, 이전에 다른 봉우리에서 먼저 같거나 작은 intensity로 방문을 했다면 pass를 할 수 있다.

 

+ 만약 다른 경로를 통해 같은 노드에 방문했다면, 저장된 값을 비교해 multiset에 넣을지 말지를 결정한다.

(intensity가 같거나 크면 multiset에 넣을 필요가 없다.)

 

​

[아이디어 정리]

1. 봉우리를 작은 순서대로 정렬하고 작은 봉우리부터 출발지에 도착할 수 있는지 탐색한다.
2. 탐색할 때, intensity가 작은 곳을 먼저 탐색해야 계산을 줄일 수 있으므로, pq, multiset, set 등을 이용해 정보를 넣을 때 마다 정렬이 되도록 한다.
3. 모든 봉우리를 탐색하고 그 중에서 가장 intensity와, mountain이 작은 값을 return한다.

 

Code

 

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

struct Cmp2
{
    bool operator()(const pair<int,int>&a, const pair<int,int>&b) const
    {
        return a.second<b.second;
    }  
};

struct Cmp
{
    bool operator()(const pair<int,int>&a, const pair<int,int>&b) const //now, inten
    {
        if (a.second==b.second)
        {
            return a.first<b.second;
        }
        return a.second<b.second;
    }  
};


vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<multiset<pair<int,int>,Cmp2>> roadMap(n+1,multiset<pair<int,int>,Cmp2>()); // node, inten;
    vector<int> mountainNode(n+1,0);//0 : 일반노드 1 : 시작노드, 2: 봉우리 노드 
    vector<int> visited(n+1,100000000);
    
    for (int i=0; i<paths.size(); i++)
    {
        vector<int>nV=paths[i];
        roadMap[nV[0]].insert(make_pair(nV[1],nV[2]));
        roadMap[nV[1]].insert(make_pair(nV[0],nV[2]));
    }
    for (int i=0; i<gates.size(); i++)
    {
        mountainNode[gates[i]]=1;
    }
    for (int i=0; i<summits.size(); i++)
    {
        mountainNode[summits[i]]=2;
    }
    vector<int> answer(2,100000000);
    
    sort(summits.begin(),summits.end());
    for (int i=0; i<summits.size(); i++)
    {
        set<pair<int,int>,Cmp> pq;
        set<pair<int,int>,Cmp>::iterator it;
        pq.insert(make_pair(summits[i],0)); //node inten
        visited[summits[i]]=0;
        pair<int,int>np,nextP;
        while(!pq.empty())
        {
            it=pq.begin();
            np=*it;
            pq.erase(it);
            if (answer[1]<=np.second)
            {
                break;
            }
            if (mountainNode[np.first]==1)
            {
                if(answer[1]>np.second)
                {
                    answer[1]=np.second;
                    answer[0]=summits[i];
                }
                break;
            }
            for (multiset<pair<int,int>>::iterator it2=roadMap[np.first].begin(); it2!=roadMap[np.first].end(); it2++)
            {
                nextP=*it2;
                if (mountainNode[nextP.first]!=2)
                {
                    int temp=max(nextP.second,np.second);
                    if (temp<visited[nextP.first])
                    {
                        pq.insert(make_pair(nextP.first,temp));
                        visited[nextP.first]=temp;
                    }
                }
            }
        }
        
    }
    
    
    return answer;
}

 

---

 

각 경로에 대해서 multiset으로 정렬을 하는 부분이 있는데, 이전에  DFS로 풀었다가 시간초과가 난 결과의 잔재다...

처음 알았는데, set에서 중복을 제거하는 기준은 bool operator에 있다.

처음에 코드를 짤 때, pair<int,int>의 구조에서 first만 비교하는 sturct를 만들었다.

그랬더니 second값이 달라도 first의 값이 같으니 중복이라고 판단해 삭제가 되는 결과가 나타났다.

set에서 중복을 어떻게 제거하는지 궁금했었는데 해결!

 

프로그래머스