Programmers 등산코스 정하기 (다익스트라)

이 문제는 2022 카카오 인턴십 코딩 테스트 문제로, 이번에 본 2024 겨울 인턴십 코딩 테스트를 대비하기 위해서 풀었던 문제이다. 처음에 dp 로 시도했다가 테스트 케이스를 다 맞추지 못해서, 다익스트라를 적용해서 간신히 풀어내었다. 다익스트라도 자꾸 시간 초과가 나서 최적화를 하는데 애먹었다. 각각의 접근 방식을 정리해두고 최종적으로 AC 받은 다익스트라 알고리즘의 최적화 방법도 남겨 놓는다.

 

---

1. 기본 아이디어

1) 정상에서 다시 입구로 갈때 중복된 간선을 이용해도 되기 때문에, 입구에서 정상까지 가는 단일한 경로만 고려한다.

2) 다른 출발점이나 정상을 경유하는 경로는 고려하지 않는다.

위 두가지 아이디어를 전제로 두고 아래와 같이 알고리즘을 짰다.

 

2. DP [틀림]

1) 각 출발점에서 dfs 로 정상까지 향한다.

2) 정점을 지날 때 최소 Intensity 값을 DP 로 기록(메모이제이션)한다. 

3) 정점 진입 시 dp 값 보다 인텐시티 값이 높으면 더이상 탐색하지 않는다.

4) 정상을 순회하며 가장 낮은 값과 출발점을 구한다.

 

사실 왜 틀렸는지 잘 모르겠다. 테스트 케이스 의 2/3 정도를 맞추고 효율성 테스트 부분에서 우수수 틀린다. 맞왜틀은 참 고통스럽다... 다음에 다시 도전해서 틀린 이유를 밝히고자 써놓음.

 

3. 다익스트라

1) 각 출발점에서 각각 다익스트라 알고리즘을 적용하여 정점을 순회한다.

2) 출발점과 정상은 경유하면 안되므로, 미리 방문 처리를 한다.

3) 우선순위 큐로 다음 방문 지점을 정한다. 

+ 최적화) 정점 방문시 현재 기록중인 최소 인텐시티 값 보다 큰 경우, 큐에 넣지 않는다.

 

이전에 풀었던 다익스트라 문제에서 시간초과를 막기위해, 최단거리를 구하고자하는 정점에 도달한 경우 더이상 방문을 진행하지 않게 하여 최적화하는 방법이 있었는데, 이런식으로 다양한 최적화 방식을 도입할 수 있다는 것을 알았다

 

작성 코드

#include <string>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Comp {
    bool operator()(const pair<int, int>& p1, const pair<int, int>& p2){
        return p1.second > p2.second;
    }
};

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    // 시작 정점에서 다익스트라 알고리즘으로 정점을 향한다.
    // 대신 다른 출발점은 스킵한다.
    
    // 최소 인텐시티부터 고르기 위해 pq 를 이용한다.
    // 방문처리를 위해 visited 를 체크
    int num_of_vertex = n;
    int num_of_path = paths.size();
    vector<pair<int, int>> path_info[n+3]; // path 정보
    for(int i=0;i<num_of_path;i++){
        int start_v = paths[i][0];
        int end_v = paths[i][1];
        int intensity = paths[i][2];
        path_info[start_v].emplace_back(end_v, intensity);
        path_info[end_v].emplace_back(start_v, intensity);
    }

    int answer1 = 987654321; // 최소 인텐시티
    int answer2; // 최소 인텐시티를 가지는 출발 정점
    for(int i=0;i<gates.size();i++){
        priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> next_vertex; // 다음에 방문할 정점 정보를 저장한다.
        bool visited[n+1]; // 방문 처리를 위한 데이터
        int intensity_info[n+1]; // 각 정점의 최소 인텐시티
        for(int j=0;j<n+1;j++){
            intensity_info[j] = 987654321;
        }
        memset(visited, false, sizeof(visited));
        
        for(int j=0;j<gates.size();j++){
            visited[gates[j]] = true; // 출발점은 방문을 못하게 한다.
        }
        
        for(int j=0;j<summits.size();j++){
            visited[summits[j]] = true; // 정상인 경우도 방문하지 못하게 한다.
        }
        
        next_vertex.emplace(gates[i], 0); // 출발점 삽입
        visited[gates[i]] = false; // 방문할 수 있도록 수정
        intensity_info[gates[i]] = 0; // 출발점은 intensity 가 0
        while(!next_vertex.empty()){
            int now = next_vertex.top().first; 
            int now_intensity = next_vertex.top().second;
            next_vertex.pop();
            if(visited[now]) continue; // 방문된 정점인 경우 스킵
            visited[now] = true; // 방문 처리
            vector<pair<int, int>> now_paths = path_info[now]; // 현재 간선 정보
            for(int j=0;j<now_paths.size();j++){
                int destination = now_paths[j].first; // 간선의 목적지
                int path_intensity = now_paths[j].second; // 간선의 인텐시티
                int new_intensity = max(path_intensity, now_intensity); // 다음 정점의 인텐시티와 비교
                if(intensity_info[destination] > new_intensity) {
                    intensity_info[destination] = new_intensity;
                    if(new_intensity <= answer1) next_vertex.emplace(destination, new_intensity);
                }
            }
        }
            // 정상의 인텐시티를 돌면서 현재 정답과 비교한다.
        for(int j=0;j<summits.size();j++){
            if(answer1 == intensity_info[summits[j]]) answer2 = min(answer2, summits[j]);
            else if(answer1 > intensity_info[summits[j]]) {
                answer1 = intensity_info[summits[j]];
                answer2 = summits[j];
            }
        }
    }
    answer.emplace_back(answer2);
    answer.emplace_back(answer1);
    return answer;
}