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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : 그래프 탐색, 다익스트라 
풀이 시간 : 31분 

문제 풀이 

n개의 지점으로 이루어져 있는 양방향 통행이 가능한 등산로가 있다. 당신은 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.

해당 규칙을 지키면서 intensity가 최소가 되는 등산코스를 정해보고, [등산 코스의 산봉우리 번호, intensity의 최솟값] 배열을 리턴하자.

 

문제에서 생각해볼 주의사항은 다음과 같다.- 한 산봉우리를 방문하였다면 다른 산봉우리를 또 방문 필요가 없다.- 처음 출발한 출입구로 돌아와야 한다.- 처음과 끝 외에 다른 출입구를 방문하면 안된다.

 

해당 문제의 예시를 보면 다음 경우와 같이 출발지 -> 산봉우리 경로와 산봉우리 -> 출발지 까지의 경로가 서로 다른 경우가 존재한다.

1 -> 5 의 경로와 5 -> 1 경로가 서로 다르다.

하지만, 다시 한 번 생각해보자. 출발지에서 산봉우리까지 가는 데 걸린 intensity가 있을 텐데, 산봉우리에서 출발한 출발지로 돌아갈 때 intensity가 더 큰 곳으로 갈 필요는 없다.

따라서, 해당 문제는 출발지에서 산봉우리까지 가는 경로들만 찾아주면 된다.

 

최소 intensity를 찾기 위해서 본 문제는 다익스트라 알고리즘으로 풀어나갈 수 있다. 여기서, $n ≤ 50000$이기 때문에, 산봉우리 정보를 미리 체크하여 다익스트라를 순회할 때 불필요한 반복문을 줄여주어야 시간 효율을 높일 수 있다.

이를 해결하기 위해 C++ STL의 `unorded_map` 라이브러리를 사용하였다. 

다익스트라를 시작하기 이전에 `unorded_map`을 통해 산봉우리 정보를 저장해주었다. 이후, 우선순위큐를 순회하며 산봉우리에 도착 시 answer 정보만 업데이트 해준 뒤 continue를 진행해주었다.

 

우선순위큐에는 모든 출발지 정보를 한번에 입력한 뒤 다익스트라를 진행해주어 한번에 모든 출발지를 확인하고자 하였다.

 

시간복잡도는 그래프 생성 + 산봉우리 정보 저장 + 다익스트라 수행 과정을 거치게 되므로 $O((N + N) * logN)$이 소요된다.

 

코드

/*
n개의 정점, 양방향 그래프
쉼터 혹은 산봉우리를 방문할 때마다 휴식 가능
휴식 없이 이동해야 하는 시간 중 가장 긴 시간 : intensity

출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 원래의 출입구로 돌아오는 등산코스
출입구는 무조건 한 곳만 방문해야함(중간에 방문 금지)

풀이 : 다익스트라
가는 부분만 체크하면 됨 : 이미 도착지까지 경로는 최소 경로임. 돌아오는데 그거보다 더 커지는 쪽으로 갈 필요 없음

*/

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

#define INF 99999999

using namespace std;


int visited[50001] = {0, };
unordered_map<int, int> summit_dict;

void dijkstra(vector<int> &gates, vector<vector<pair<int, int>>> &graph, vector<int> &answer){
    priority_queue<pair<int, int>> pq;
    for (auto su : gates){
        pq.push({0, su});
        visited[su] = 0;
    }
    
    while (!pq.empty()){
        int w = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (w > answer[1])
            continue;
        // cout << u << ' '<< w << '\n';
        if (summit_dict[u]){
            if (w < answer[1])
                answer = {u, w};
            else if (w == answer[1])
                answer[0] = min(answer[0], u);
            // cout << answer[0] << " ans " << answer[1] << '\n';
            continue;
        }
        
        for (auto v : graph[u]){
            int new_cost = max(w, v.second);
            if (visited[v.first] > new_cost){
                pq.push({new_cost, v.first});
                visited[v.first] = new_cost;
                // cout << v.first << "   "<< visited[v.first] << '\n';
            }
        }
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    answer.push_back(0);
    answer.push_back(INF);
    vector<vector<pair<int, int>>> graph(n + 1);
    
    // 그래프 생성
    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]});
    }
    
    // visited 초기화
    for (int i=0;i<n + 1;i++){
        visited[i] = INF;
    }
    
    // 산봉우리 미리 표시
    for (auto su : summits){
        summit_dict[su] = 1;
    }
    
    dijkstra(gates, graph, answer);
    
    
    return answer;
}

배운 점 

챗지피티한테 실행 시간을 단축시킬 방법이 있는지 물어봤는데 해시맵 대신 set을 추천해주었다.

set과 unorded_map 모두 레드-블랙 트리를 기반으로 값을 찾아서 실행시간에 차이가 있나 싶었지만, 

map은 `key-value` 쌍 정보를 모두 저장해야 하기 때문에 불필요한 메모리 오버헤드를 발생하여 캐시 효율을 저하시키기 때문에, 단순히 0 or 1을 사용하기 위해서는 set이 더 효과적이라고 한다.

 

set을 사용한 적은 많이 없는데 틈틈히 공부해야겠다.

 

+ set 대신 dat 배열을 사용해서 배열 주소에 직접 접근 하는 방식을 사용한다면 시간 효율이 더 좋아졌다 !