[프로그래머스][C++] 등산코스 정하기 (248)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

프로그래머스

 

생각의 흐름

그레프 문제인건 확실한데, 처음 보면 익숙하면서 조금 어색한 느낌도 들고... 어떠한 방식으로 풀어야할지 한눈에 보이지는 않았다.

 

이 문제는 생각할점이 3가지나 존재합니다.

1) 알고리즘

2) 편도와 왕복

3) 시간복잡도 생각하기

 

1 - 1) 알고리즘

그러다 "다익스트라" 알고리즘이 필요함을 깨닫게 되는 부분이 있었다.

 

우선 원래 "다익스트라"알고리즘의 목적을 생각해보자.

=> 한 정점으로부터 다른 모든 정점까지의 최단거리 구하기 위해 사용

 

이번 우리 문제의 목적을 생각해보자.

=> 한 정점(출입구) 으로부터 정상(도착지점) 까지 가는데 필요한 Intensity의 최소값

 

이때 다익스트라가 필요함을 느꼈습니다. 다만 일반적인 다익스트라와는 다르게, 가중치의 갱신을 누적합이 아닌 최댓값 비교를 이용해야 합니다.

 

추가적으로 주어진 그레프도 모두 양의 간선으로 구성되어 있었으니 매우 적합하다 생각하 바로 적용하였습니다.

 

1 - 2) 편도와 왕복

원래 문제는 (출입구 - 산봉우리 - 출입구)를 이동하는 동안 최소 intensity를 구하는 문제입니다.

하지만 (출입구 - 산봉우리)의 최소 intensity가 결국 (산봉우리 - 출입구)의 최소 intensity이기 때문에 (출입구 - 산봉우리)를 이동하며 최소 intensity를 구하면 됩니다.

 

이는 당연한게 그래프가 양뱡향 그래프이며, 방향에 따라 비용이 다르지 않습니다.

양뱡향 모두 비용이 같기 때문에 (출입구 - 산봉우리) 와 (출입구 - 산봉우리) 의 intensity가 같을수밖에 없습니다.

 

여기까지만 생각해서 모든 시작점을 기준으로 다익스트라를 돌면 되겠다라고 생각했습니다만... 크나큰 문제가.....

 

1 - 3) 시간복잡도

사실 마지막 이 부분은 스스로 생각하지 못했습니다. 시간복잡도 계산좀 습관화 해야 하는데...

 

• vertex의 갯수 |V|의 최댓값 = 50,000
• edge의 갯수 |E|의 최댓값 = 200,000
• 우선순위 큐를 사용한 dijkstra의 시간복잡도 = O(|E|log|V|)

이 때 각 gate별로 다익스트라를 수행하므로, 지금까지의 풀이의 총 시간복잡도는 |V| * O(|E|log|V|) 로,

최악의 경우 약 50,000,000,000회의 연산을 수행하게 됩니다.

 

1억번 = 1초 (요즘은 4억번 까지 1초에 가능)라 쳐도 500초 정도가 소요되므로 시간 초과는 당연한 것 이였습니다.

 

따라서 모든 출입구에서 다익스트라를 적용하려 했던 방식을 변경해야 했습니다.

 

이 문제는 어디서 출발하던 하나의 최솟값만을 찾으면 됩니다.

그렇다면 모든 gate에서 동시에 출발하여 intensity를 기록하는 배열을 공유시키고, 어디서 출발한 경로이건 상관없이 최소값만 찾으면 됩니다.

 

따라서 다음과 같이 모든 시작지점을 한번에 우선순위 큐에 삽입한 후 시작하면 됩니다.

for(auto g : gates) {
    pq.push({0, g});
    intensity[g] = 0;
}

 

따라서 총 시간복잡도는 다익스트라의 시간복잡도와 일치하는 O(|E|log|V|)로, 최악의 경우에도 약 백만 번의 연산만으로 문제를 해결할 수 있습니다.

 

나의 코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
#define MAX 50001

using namespace std;

vector<int> res;
vector<pair<int, int>> adj[MAX];
int intensity[MAX];
bool isSummit[MAX];

void go(vector<int>& gates) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<pair<int, int>> temp;
    
    memset(intensity, -1, sizeof(intensity));
    
    for(auto g : gates) {
        pq.push({0, g});
        intensity[g] = 0;
    }
    
    while(!pq.empty()) {
        int cost = pq.top().first;
        int nowV = pq.top().second;
        pq.pop();
        
        if(cost > intensity[nowV]) continue;
        
        if(isSummit[nowV]) {
            temp.push_back({cost, nowV});
            continue;
        }
        
        for(auto p : adj[nowV]) {
            int weight = p.first;
            int to = p.second;
            
            if(intensity[to] == -1 || max(cost, weight) < intensity[to]) {
                intensity[to] = max(cost, weight);
                pq.push({intensity[to], to});
            }
        }
    }
    
    sort(ALL(temp));
    res.push_back(temp[0].second);
    res.push_back(temp[0].first);
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    
    for (auto e : paths) {
        adj[e[0]].push_back({e[2], e[1]});
        adj[e[1]].push_back({e[2], e[0]});
    }
    
    for(auto s : summits) {
        isSummit[s] = true;
    }
    
    go(gates);
    return res;
}