[c++][프로그래머스] 등산코스 정하기

프로그래머스 등산코스 정하기 [2022 KAKAO TECH INTERNSHIP]
https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

문제 풀이

• 이 문제는 다익스트라 알고리즘을 사용해 풀었습니다. 문제는 출입구 - 산봉우리 - 출입구를 이동하는 동안 최소 intensity를 구하는 문제이지만 출입구 - 산봉우리의 최소 intensity가 결국 산봉우리 - 출입구의 최소 intensity이기 때문에 출입구 - 산봉우리를 이동하며 최소 intensity를 구하는 것을 기준으로 다익스트라 알고리즘을 구현합니다.
• 각 지점에 도달했을 때 가질 수 있는 최소 intensity를 저장하는 intensity[] 배열을 선언해 더 이동할지, 멈출지를 결정합니다. 현재 최소 intensity보다 더 작은 intensity로 해당 지점에 도달한 적이 있다면 더 이상 진행할 필요가 없기 때문입니다.

코드

#include <vector>
#include <queue>

using namespace std;

int nodes[50010];
int intensity[50010];
vector<vector<pair<int,int>>> graph(50010);

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
  for(int i=1; i<=n; ++i) intensity[i] = 1e8;
  for(auto s: summits) nodes[s] = 2;
  for(auto p: paths) {
    graph[p[0]].push_back({p[2], p[1]});
    graph[p[1]].push_back({p[2], p[0]});
  }

  priority_queue<pair<int,int>> pq;
  for(auto g: gates) {
    intensity[g] = -1; // 다른 출입구로 이동하는 것을 방지하기 위해 -1 넣어줌
    pq.push({0, g});
  }
    
  int ans_intensity = 1e9;
  int summit = 1e9;

  while(!pq.empty()) {
    auto [max_intensity, cur_node] = pq.top(); pq.pop();
    
    if(max_intensity > ans_intensity) continue;
    if(nodes[cur_node] == 2) {
      if(max_intensity < ans_intensity) {
        ans_intensity = max_intensity;
        summit = cur_node;
      }
      else if(max_intensity == ans_intensity && cur_node < summit) {
        summit = cur_node;
      }
      continue;
    }

    for(auto next: graph[cur_node]) {
      if(intensity[next.second] > max(max_intensity, next.first)) {
        intensity[next.second] = max(max_intensity, next.first);

        pq.push({intensity[next.second], next.second});
      } // 현재 최소 intensity보다 작게 도달한 적이 있다면 pass
    }
  }

  return {summit, ans_intensity};
}

실행 결과