[프로그래머스 LV3/C++] 알고리즘 - 등산 코스 정하기

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘  등산 코스 정하기를 풀어보도록 하겠습니다.

 

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

 

[문제 접근]

휴식 없이 이동해야 하는 시간 중 가장 긴 시간인 intensity를 숙지하는 게 제일 중요합니다. 저는 이를 잘못이해하면 풀이를 하는데 시간을 많이 잡아먹었습니다. 여러 출입구 와 산봉우리가 있는데, 출입구에서 산봉우리까지 이동하면 intensity들을 파악하고 이 intensity들 중에서 가장 최소인 intensity를 경로 중에 가지고 있는 산봉우리의 번호를 찾아야 합니다. 이때 intensity가 같다면 산봉우리번호가 작은 것이 정답입니다. intensity의 정의와 구하고자하는 것이 헷갈리지 않도록 유의해야 합니다.

 

이를 이해하고, 어떤 알고리즘을 이용하여 풀어야할 지 생각해볼 때,

출입구라는 정점에서 여러 산봉우리 정점까지의 가장 긴시간인 intensity를 구하는 것이 다익스트라 알고리즘이랑 매우 흡사합니다.

역시 카카오는 개념을 약간 응용해서 문제를 내네여. (여기서 여러 출입구랑 여러 산봉우리니까 플로이드 워셜 알고리즘도 생각했지만 n이 50000만이하라서 시간복잡도 측면에서 패스)

다익스트라 알고리즘 간선을 지날때마다 최단거 리를 고려하니까, 이 문제는 간선을 지날때마다 intensity를 지나면 되겠네여.

 

[풀이 전략]

1. 정점과 간선을 포함하는 paths를 인접리스트로 정리한다.

2. 정점을 지나면서 산봉우리가 아닐때만 다음 정점을 지나도록 isSummit[산봉우리번호]로 정의하고 초기화한다.

3. 다익스트라 알고리즘을 구현한다.

-  for(auto gate: gates)을 활용하여 하나씩 산봉우리들을 살펴보지 말고, 그냥 한 번에 queue에 담는다.( 이렇게 하면 거리를 저장할 배열을 하나만 만들면 된다)

- 최단거리가 아니라 매 간선을 지날때마다 intensity를 체크해준다.

 

[코드]

#include <vector>
#include <queue>
#include <algorithm>

#define X first
#define Y second

using namespace std;

const int INF = 20'000'000 ;
vector<pair<int,int>> adj[50'001]; // 최단거리 테이블

bool isSummit[50001];

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for(auto s : summits) isSummit[s] = true ;
    
    for(auto path: paths) {
        adj[path[0]].push_back({path[2],path[1]});
        adj[path[1]].push_back({path[2],path[0]});
    }
    
  
        int d[50'001];
        fill(d,d+n+1,INF);
        
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq ; 
        for(auto gate: gates) {
        d[gate] = 0 ;
        pq.push({d[gate],gate});
    }

        
        while(!pq.empty()) {
            auto cur = pq.top(); pq.pop();
            if(d[cur.Y] != cur.X) continue;
        
            for(auto nxt : adj[cur.Y]) {

                if(d[nxt.Y] <= max(d[cur.Y],nxt.X)) continue;
                d[nxt.Y] = max(d[cur.Y],nxt.X);
                if(!isSummit[nxt.Y])
                    pq.push({d[nxt.Y],nxt.Y});
            }
        }
    
    vector<int> answer ;
    
    int ans = summits[0];
    
    for(auto s: summits) {
        if(d[s] < d[ans]) ans = s;
        else if(d[s] == d[ans] && s < ans) ans =s ;
    }
    answer.push_back(ans);
    answer.push_back(d[ans]);

    return answer;
}

 

 

 

[배울점]

- 문제 꼼꼼히 이해하기

- 테스트 실행하기 전에 머릿속으로 엣지케이스 시뮬레이션하기