[Algorithm] 프로그래머스 - 등산코스 정하기

문제

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

사용 알고리즘

- 다익스트라

해결방법

• (출발지 - 산봉우리 - 출발지) 해당 등산 루트에서 intensity 가 가장 작은 경로를 구해야 하는데 해당 문제는 양방향 그래프이므로 (출발지 - 산봉우리) 편도만 확인해도 된다. 
  • intensity == 휴식 없이 이동해야 하는 시간 중 가장 긴 시간
• 모든 출발지들을 우선순위 queue에 넣고 탐색을 시작한다.
• 탈출 조건
  • 해당 지점에서의 intensity가 이미 구해진 경우 
  • 산봉우리에 도착한 경우
    • temp 큐에 산봉우리 번호와 비용(intensity)를 저장한다.

테스트케이스 1번

now: 1 to: 2 cost: 0 weight: 3 pq.push(3, 2) now: 3 to: 4 cost: 0 weight: 4 pq.push(4, 4) now: 2 to: 4 cost: 3 weight: 2 pq.push(3, 4) now: 2 to: 5 cost: 3 weight: 4 pq.push(4, 5) now: 4 to: 5 cost: 3 weight: 3 pq.push(3, 5) now: 4 to: 6 cost: 3 weight: 1 pq.push(3, 6)

 

 

소스코드

사용언어 : C++

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

using namespace std;

vector<int> answer;
vector<pair<int,int>> graph[MAX]; //{비용, 다음지점}
int intensity[MAX]; // 각 지점에 도달하는 동안 최소 intensity(비용)
bool is_summit[MAX]; // 산봉우리 배열


void dijkstra(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; // g까지 경로 중 최소 비용(intensity)
    }
    
    while(!pq.empty()) {
        int cost = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        if (cost > intensity[now]) continue; // 이미 최소 비용을 구한 경우
        
        if (is_summit[now]) { // 봉우리 도착인 경우, 비용과 봉우리 위치 저장
            temp.push_back({cost, now});
            continue;
        }
        
        for (auto g : graph[now]) {
            int weight = g.first; //now에서 to로 이동하는 비용
            int to = g.second;
            
            // 방문 전 또는 경유하는게 더 최소비용일 경우
            // intensity를 구해야하므로 max(cost, weight) 사용
            if (intensity[to] == -1 || max(cost, weight) < intensity[to]) {
                intensity[to] = max(cost, weight);
                pq.push({intensity[to], to});
            }
        }
    }
    
    sort(ALL(temp)); // cost 오름차순 정렬
    answer.push_back(temp[0].second);
    answer.push_back(temp[0].first);
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    
    // 그래프 정보 저장
    for (auto p : paths) {
        graph[p[0]].push_back({p[2], p[1]});
        graph[p[1]].push_back({p[2], p[0]});
    }
    
    // 산 봉우리 정보 저장
    for (auto s : summits) {
        is_summit[s] = true;
    }
    
    dijkstra(gates);
    
    return answer;
}

<bits/stdc++.h>

* #include <bits/stdc++.h> 헤더파일 사용하기

* 자주 사용하는 라이브러리들(vector, algorithm, string, queue, 등 .. )을 컴파일하도록 함

* 표준 라이브러리가 아니므로 파일을 따로 추가해 주어야 사용 가능하다.

* 자주 사용하는 라이브러리들을 전부 컴파일함으로, 사용하지 않거나 불필요한 라이브러리들도 컴파일되므로 그만큼 시간이나 공간이 낭비됨.

 

우선순위 큐

* priority_queue

 

한줄평

다익스트라 알고리즘을 처음 공부해보았다. c++의 우선순위 큐를 사용하는 것도 처음인데, ,  시간복잡도가 O(logN)인 점에서 굉장히 효율적인 알고리즘인 것 같다.

 

참고 블로그

https://blogshine.tistory.com/564

https://charles098.tistory.com/11