[Algorithm] Programmers :: 등산코스 정하기

https://school.programmers.co.kr/learn/courses/30/lessons/118669?language=cpp 

프로그래머스

 

 

const int MAX_NUM = 0x3f3f3f3f;
 
struct Node
{
    int node;
    int weight;
};
 
struct cmp
{
    bool operator()(const Node& a, const Node& b)
    {
        return a.weight > b.weight;
    }
};
 
vector<vector<Node>> graph(50001);
int intensityArray[50001] = { 0 };
bool isSummit[50001] = { false };
bool isGate[50001] = {false};
 
pair<int, int> GetResult(vector<int> startNodes, vector<int>& summits)
{
    memset(intensityArray, 0x3f, sizeof(intensityArray));
 
    priority_queue<Node, vector<Node>, cmp> pq;
 
    for (int i = 0; i < startNodes.size(); ++i)
    {
        pq.push({ startNodes[i],0 });
        intensityArray[startNodes[i]] = 0;
    }
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        int curIntensity = pq.top().weight;
        pq.pop();
 
        if (curIntensity > intensityArray[curNode]) continue;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextWeight = graph[curNode][i].weight;
            int nextIntensity = curIntensity > nextWeight ? curIntensity : nextWeight;
 
            if (isGate[nextNode]) continue;
            if (isSummit[nextNode]) // 산봉우리면 값 업데이트 하더라도 큐에는 넣지않는다.
            {
                if (nextIntensity < intensityArray[nextNode])
                {
                    intensityArray[nextNode] = nextIntensity;
                }
 
                continue;
            }
 
            if (nextIntensity < intensityArray[nextNode])
            {
                intensityArray[nextNode] = nextIntensity;
                pq.push({ nextNode,nextIntensity });
            }
        }
    }
 
    int summit = 0;
    int intensity = MAX_NUM;
 
    for (int i = 0; i < summits.size(); ++i)
    {
        int n = summits[i];
 
        if (intensityArray[n] < intensity)
        {
            intensity = intensityArray[n];
            summit = n;
        }
    }
 
    return { summit,intensity };
}
 
 
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
 
    vector<int> answer = { 0,MAX_NUM };
    sort(summits.begin(), summits.end());
 
    for (int i = 0; i < gates.size(); ++i)
    {
        isGate[gates[i]] = true;
    }
    
    for (int i = 0; i < summits.size(); ++i)
    {
        isSummit[summits[i]] = true;
    }
 
    for (int i = 0; i < paths.size(); ++i)
    {
        graph[paths[i][0]].push_back({ paths[i][1],paths[i][2] });
        graph[paths[i][1]].push_back({ paths[i][0],paths[i][2] });
    }
 
    pair<int, int> result = GetResult(gates, summits);
    answer[0] = result.first;
    answer[1] = result.second;
 
    return answer;
}

베이스는 다익스트라이며, 다익스트라가 수행하는 로직을 잘 이해하고 있다면 접근자체는 어렵지 않을 것 같다.

기존의 다익스트라에서 dist[node]의 경우는 node까지 갈 수 있는 '최소의 거리'이지만

이 문제에서 dist[node]와 대응되는 intensityArray[node]의 경우는 node까지의 '최소의 intensity'이다

intensity란 해당 노드까지 거쳐간 간선 중 최대 거리(weight)를 말한다.

이것부터 잘 인지하고 있어야한다.

 

먼저 모든 출발점 -> 산봉우리까지의 최소 intensity값만 구하면 된다.

최소Intensity를 보장한다면, 갔던길을 통해 다시 출발점까지 오면 되기 때문에 산봉우리 -> 출발점에 대해서는 어떠한 로직도 수행할 필요가 없다.

 

그리고 산봉우리노드에 대해서는 미리 체크해놓는다.

큐에 넣을 때 intensity값체크하는거는 산봉우리노드든 일반노드든 똑같지만, 산봉우리노드의 경우에는 pq(우선순위큐)에 더이상 인접노드를 넣으면 안되기 때문이다. 산봉우리까지가 목표였기 때문에 더이상 퍼뜨리면 안된다.

그렇기 때문에 바로 continue를 해준다.

 

비슷한 이유로 출입구노드에 대해서도 미리 체크한 후, nextNode가 출입구노드일 경우 바로 continue 한다.

어차피 경로에 출입구가 있으면 안되기 때문에 출입구노드를 큐에넣을 필요는 없다.

다만, 바로 continue안하더라도 로직상 큐에 들어갈 일은 없기 때문에 이부분은 검사를 안해줘도 상관없다.

이미 intensityArray[출입구]에는 0이라는 최저의 값이 들어가있기 때문에 방문되어질 일은 전혀 없다.

실제로 검사 한거랑 안한거랑 수행속도는 거의 차이가 없었다. (동일하다고 봐도 될정도)

심지어 검사하려면 isGate라는 50001바이트만큼의 배열을 추가선언해야하기 때문에 이 문제에 한해서는 안하는게 메모리효율은 더 좋다.

 

intensityArray에 값업데이트를 위한 nextIntensity값은 조건에 따라 다르다. (위코드에서는 삼항연산자로 체크했다)

다음 노드까지의 weight가 현재노드까지 이어져온 curIntensity값보다 작을 경우, intensity값으로 값업데이트를 한다.

왜냐하면 intensity란 해당 경로에서의 최대 weight값이여야만 하기 때문이다.

만약 nextNode까지의 weight가 curIntensity보다 더 클 경우, nextNode의 weight가 해당경로에서의 새로운 Intensity가 되는것이다. 먼저 이걸 정해준 다음, intensityArray에 값업데이트를 시도하는 것이다.

 

그리고 중요한것 중 하나는, 각 출발점마다 위의 로직을 수행할 것이 아니라 그냥 출발점을 전부 pq에 넣어야 한다는 것이다. 왜냐하면 시간초과때문에 그렇다.

다익스트라는 E log V의 시간복잡도를 가진다. 이 문제에서 V는 최대 5만, 간선은 최대 10만개이기 때문에 

50,000 * 200,000 * log 50,000 이 된다. log 50,000이 15.6? 정도 되니까 약 1560억번의 수행횟수가 나온다.

그렇기 때문에 반드시 시간초과가 발생하며, 이에 따라 획기적으로 횟수를 줄여야한다.

 

그러기위한 아이디어가 출발점노드를 전부 다 넣고 다익스트라를 수행하는 것이다.

어떻게보면 처음부터 충분히 접근해볼만한 방법이였다. 다익스트라 라는 알고리즘의 로직을 잘 이해하고 있다면 말이다.

이제는 이 문제를 풀어봤기 때문에, 다른 문제를 풀 때 쉽게 접근할 수 있을것이다.

어쨌든 한 번의 다익스트라만 수행하면 되기 때문에 E log V 로 수행이 가능하며, 충분히 시간제한안에 로직은 수행된다.

다른 풀이글들과 비교해보더라도 꽤 괜찮은 수행속도가 나온 것 같다.

 

그리고 이번 문제처럼 해당 노드가 어떤 상태인지를 체크하기위한 isSummit같은 컨테이너를 사용해야 한다고 했을 때,

최대한 map같은것은 배제하는게 좋다. 메모리여유가 된다는 가정하에 무조건 배열을 사용하는게 좋다.

처음에 산봉우리와 출발지노드인지의 상태를 저장하기 위해 map에다가 저장해놨다가 나중에 위 코드처럼 배열로 저장 후, 검사했는데 수행속도가 꽤 많이 차이난다.

map도 랜덤액세스의 수행속도가 느린 편은 아니지만, 역시 배열보다 빠를 순 없기 때문이다.

아마 unordered_map을 사용했더라면 map보다는 더 빠르긴 했겠지만 어차피 배열보단 느리다.