[프로그래머스/Level 3/C++/2022 카카오 TECH 인턴십] 등산코스 정하기

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다.

 

- 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.

 

- 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.

- 예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.

- 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.

 

- 당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 합니다.

 

- 다음은 XX산의 지점과 등산로를 그림으로 표현한 예시입니다.

• 위 그림에서 원에 적힌 숫자는 지점의 번호를 나타내며, 1, 3번 지점에 출입구, 5번 지점에 산봉우리가 있습니다. 각 선분은 등산로를 나타내며, 각 선분에 적힌 수는 이동 시간을 나타냅니다. 예를 들어 1번 지점에서 2번 지점으로 이동할 때는 3시간이 소요됩니다.

- 위의 예시에서 1-2-5-4-3 과 같은 등산코스는 처음 출발한 원래의 출입구로 돌아오지 않기 때문에 잘못된 등산코스입니다.

- 또한 1-2-5-6-4-3-2-1 과 같은 등산코스는 코스의 처음과 끝 외에 3번 출입구를 방문하기 때문에 잘못된 등산코스입니다.

- 등산코스를 3-2-5-4-3 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

- 이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 5시간입니다. 따라서 이 등산코스의 intensity는 5입니다.

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

- 이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 3시간입니다. 따라서 이 등산코스의 intensity는 3이며, 이 보다 intensity가 낮은 등산코스는 없습니다.

 

[문제 조건]

• 2 ≤ n ≤ 50,000
• n - 1 ≤ paths의 길이 ≤ 200,000
• paths의 원소는 [i, j, w] 형태입니다.
  • i번 지점과 j번 지점을 연결하는 등산로가 있다는 뜻입니다.
  • w는 두 지점 사이를 이동하는 데 걸리는 시간입니다.
  • 1 ≤ i < j ≤ n
  • 1 ≤ w ≤ 10,000,000
  • 서로 다른 두 지점을 직접 연결하는 등산로는 최대 1개입니다.
• 1 ≤ gates의 길이 ≤ n
  • 1 ≤ gates의 원소 ≤ n
  • gates의 원소는 해당 지점이 출입구임을 나타냅니다.
• 1 ≤ summits의 길이 ≤ n
  • 1 ≤ summits의 원소 ≤ n
  • summits의 원소는 해당 지점이 산봉우리임을 나타냅니다.
• 출입구이면서 동시에 산봉우리인 지점은 없습니다.
• gates와 summits에 등장하지 않은 지점은 모두 쉼터입니다.
• 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.
• return 하는 배열은 [산봉우리의 번호, intensity의 최솟값] 순서여야 합니다.

 

[문제 풀이]

문제에서 원하는 것은 출입구 - ... - 산봉우리 - ... - 출입구 의 경로에서 가장 큰 intensity를 가지면서 이 intensity를 최소로 하는 등산코스를 찾는 것이 목적이다.

 

잘 생각해보면 출입구(A)에서 산봉우리(B)까지 intensity 최소가 되도록 가는 길을 찾았다면 산봉우리(B)에서 같은 출입구(A)로 다시 되돌아 오는 방법이 intensity를 최소로 하는 방법일 것이다.

 

그래서 필자는 산봉우리를 기준으로하여 다익스트라 방법을 이용해 각 정점까지 이동하는데 드는 최소 intensity를 구하고 정점들 중 출입구들만 골라서 계산된 intensity값을 오름차순으로 정렬하여 그 중 가장 작은 값을 answer에 갱신시키면서 모든 산봉우리에 대하여 계산을 하면 정답이된다.

 

또한 문제에서 최소가 되는 intensity가 여러개일 경우 산봉우리의 값이 작은 경우를 출력해야하기 때문에 먼저 summits 배열을 오름차순으로 정렬시킨 뒤 구해진 답과 비교하여 새로운 값이 더 작을때만 갱신하도록 해서 "값이 작은 산봉우리를 출력" 조건을 해결했다.

 

그리고 또 다른 문제로는 시간초과가 자주 발생하는데 이 부분은 이미 구해진 정답보다 intensity 더 커지는 경로를 더 탐색하지 않게 했다.

 

[소스 코드]

#include <string>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>

#define pii pair<int,int>
#define INF 987654321

using namespace std;

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer; answer.push_back(-1); answer.push_back(INF);
    vector<vector<pii>> graph; graph.resize(n+1);
    
    //산봉오리 정점인지 아닌지 판별용
    vector<bool> ck_summits(n+1);
    for(int i=0; i<summits.size(); i++) ck_summits[summits[i]]=true;
    
    //양방향 인접리스트 생성
    for(int i=0; i<paths.size(); i++)
    {
        graph[paths[i][0]].push_back({paths[i][1], paths[i][2]});
        graph[paths[i][1]].push_back({paths[i][0], paths[i][2]});
    }
    
    //작은 산봉오리 순서대로
    sort(summits.begin(), summits.end());
    for(int i=0; i<summits.size(); i++)
    {
        int top = summits[i];
        
        //다익스트라
        vector<int> distance(n+1, INF);
        priority_queue<pair<int,int>> pq;
        distance[top] = 0;
        pq.push({top, 0});
        while(!pq.empty())
        {
            pair<int,int> tmp = pq.top(); pq.pop();
            int cur_node = tmp.first;
            int intensity = -tmp.second;
            
            for(int j=0; j<graph[cur_node].size(); j++)
            {
                int next = graph[cur_node][j].first;
                int next_intensity = graph[cur_node][j].second;
                if(ck_summits[next]) continue;
                if(max(intensity,next_intensity) < distance[next])
                {
                    distance[next] = max(intensity, next_intensity);
                    if(answer[1] < distance[next]) continue;
                    pq.push({next, -distance[next]});
                }
            }
        }
        
        //가장 작은 intensity를 찾음
        int ans = INF;
        for(int j=0; j<gates.size(); j++) ans = min(ans, distance[gates[j]]);
        
        //갱신
        if(ans < answer[1])
        {
            answer[0] = summits[i];
            answer[1] = ans;
        }
        
        //1보다 클 순 없음
        if(answer[1] == 1) break;
    }
    
    
    return answer;
}

굳