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

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

프로그래머스

풀이

처음 봤을 때 다익스트라 문제 같았지만 경로 intensity 총합의 최소가 아닌, gate에서 출발해 summit으로 도달하는 경로 중 최대 intensity가 최소가 되도록 하는 경로의 산봉우리와 intensity를 구하는 것이었다. 

고민을 좀 하다가 카카오 공식 풀이를 참고했다...하하.. 

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

2022 테크 여름인턴십 코딩테스트 해설

문제의 핵심은 세 가진데,

 

1. 어느 gate에서 어느 summit으로 가든, 즉 어느 경로로 가든 최소 intensity와 그 때 도착하는 summit만 알면 된다. 

우선순위 큐에 모든 gate를 넣고 한번에 돌려 시간 제한을 막을 수 있습니다. 정점에 도달하는 최소 가중치를 저장하는 intensity 배열을 사용해 최종 답을 구할 수 있습니다.

 

2. gate에서 summit로 가는 최대 intensity가 최소가 되는 경로를 찾았다면 다시 gate로 갈 때는 해당 경로로 가면 되므로 편도 경로만 찾으면 됩니다.

 

3. 기존의 다익스트라 알고리즘에서 from 정점에서 to 정점으로 가는 가중치가 weight 인 간선이 있을 때 최단 거리 배열 dist의 갱신 방법은 아래와 같습니다.

 

if ( dist[to] > dist[from] + weight ) then

dist[to] = dist[from] + weight 

 

이 문제에서는 경로의 최대 weight를 저장하는 intensity배열을 선언하게 되는데, 항상 경로의 최대 값으로 갱신 됩니다. 

 

즉, (카카오 해설) 임의의 출입구 A에서 시작해 각 지점까지의 intensity 배열을 점점 채워나간다고 생각해봅시다. 경로에 포함된 등산로들의 w값 중 최댓값이 경로의 intensity이기 때문에, 등산로를 더 지날수록 경로의 intensity는 단조 증가하는 형태를 띕니다(예를 들어, A-B-C 경로의 intensity가 3이라면 A-B-C-D 경로의 intensity가 3보다 작아질 수는 없습니다). 경로의 가중치가 단조 증가하는 성질 덕분에 다익스트라 알고리즘을 변형하면 intensity 배열을 채우는 알고리즘을 만들 수 있습니다.

 

따라서, 기존의 갱신 방법에서 아래와 같이 변형해 현재 지점까지의 weight와 다음 지점의 weight를 비교해 더 큰 값이 이미 저장된 다음 지점의 가중치 보다 작다면(최대 값이 최소가 되도록) 저장하도록 intensity 배열을 갱신할 수 있습니다.

 

if ( intensity[to] > max( intensity[from], weight ) ) then

intensity[to] = max ( intensity[from], weight ) ) 

 

리뷰

어려운 듯 했으나 이해하고 나면 아... 하는 문제였다. 역시 카카오 문제가 실력 향상에 많은 도움이 되는 것 같고 다익스트라로 할 수 있는게 하나 늘었다.

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#define MAX 987654321

using namespace std;

struct Node{
    int vex;
    int intensity;
    Node (int a, int b) {
        vex=a;
        intensity=b;
    }
    bool operator<(const Node& b) const {
        return intensity > b.intensity;
    }
};

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<pair<int, int>> graph[n+1];
    vector<int> isSummit(n+1, 0);
    vector<int> intensity(n+1, MAX);

    for (auto i : summits) isSummit[i]=1;
    for (auto p : paths) {
        graph[p[0]].push_back({p[1], p[2]});
        graph[p[1]].push_back({p[0], p[2]});
    }
    
    priority_queue<Node> pq;
    for (int i=0; i<gates.size(); i++) {
        pq.push(Node(gates[i], 0));
        intensity[gates[i]] = 0;
    }
    
    while (!pq.empty()) {
        int from = pq.top().vex;
        int cost = pq.top().intensity;
        pq.pop();
        // 최솟값이라고 나온게 이미 저장 된 것보다 크다면 할 필요 없음
    	if (cost > intensity[from]) continue;
        if (isSummit[from]) continue;
        
        for (auto next : graph[from]) {
            int to = next.first;
            int ncost = next.second;
            // intensity 는 단조 증가, 현재와 다음 값을 비교해서 더 큰 값을 to에 넣으면 됨
            if (intensity[to] > max(intensity[from], ncost)) {
                intensity[to] = max(intensity[from], ncost);
                pq.push(Node(to, intensity[to]));
            }
        }
    }
    
    int min_intensity=MAX;
    int idx=0;
    for (int i=1; i<intensity.size(); i++) {
        if (isSummit[i]) {
            if (min_intensity > intensity[i]) {
                min_intensity = intensity[i];
                idx = i;
            }
        }
    }
    
    return {idx, min_intensity};
}