[프로그래머스 lv3] 등산 코스 정하기 풀이

해설

해당 문제는 2022 KAKAO TECH INTERNSHIP 문제로 아래 사이트에 공식 해설이 있습니다.

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

 

1) 등산 코스는 출발 지점에서 시작하여 쉼터를 지나고(여러개 가능) 산봉오리를 지나 다시 쉼터를 지나고 출발지점으로 와야 한다.

이 때, 출발 지점에서 산봉오리를 지난 후 다시 돌아오는 길은 올라갔던 길과 동일하게 내려오면 되므로 출발 지점 -> 산봉오리까지의 경로만 생각하면 된다. 즉, 이 문제는 출발 지점에서 산봉오리까지 도달할 때 최소 intencity를 구하는 문제이다.

 

2) 산봉오리는 중간에 여러개를 찍으면 안되고, 마지막 하나만 찍어야 한다. 이러한 조건을 만족시키려면, 간선 (x, y)가 주어졌을 때, 출발지점에서는 나가는 그래프만, 산봉오리에서는 들어오는 그래프만 취급해야 한다. 출발지점에서는 나가기만 하고, 산봉오리에서는 들어오기만 하면 두 개의 산봉오리를 거쳐 이동하는 상황이나, 다른 출발지점으로 들어가는 상황을 막을 수 있다.

 

3) intencity[i] = 출발 지점에서 i번째 노드까지 이동할 때, 최소 intencity 값 이라고 가정하자.

출발지점에서 i번째까지 가는 여러 경로가 있다. 이 때, 각각의 경로에서 가장 긴 간선의 길이를 intencity라고 한다. 

intencity[i]는 여러개의 intencity 중에서 최솟값을 의미한다.

 

4) intencity[i]는 다익스트라 알고리즘으로 구할 수 있다.

다익스트라는 A지점에서 B지점으로 이동하는 최단 거리를 구하는 알고리즘인데, dist[from]+weight < dist[to] 일 경우, dist[to] = dist[from]+weight 로 변환한다.

다익스트라를 변형해서, 출발지로 부터 특정 노드 i까지 이동할 때 최소 intencity의 값을 intencity[i] 라고 하자.

max(intencity[from], weight) < intencity[to] 이면 intencity[to] = max(intencity[from], weight) 으로 변경한다.

 

(다익스트라 관련 포스트: 최단거리구하기_다익스트라(Dijkstra) 알고리즘)

(다익스트라 관련 추천 강의: [바킹독의 실전 알고리즘] 0x1D강 - 다익스트라 알고리즘)

 

5) 모든 출발지에서 각각 다익스트라를 돌리면 시간초과가 발생한다. 가장 처음 우선순위큐에 모든 출발지점을 넣고 다익스트라는 한번만 실행하자. 우리는 경로 정보나 출발지 정보가 필요없다. 출발지까지의 intencity[x] = 0으로 모두 초기화하여 "여러 출발지"로 부터 특정 노드까지의 intencity 최솟값을 구하면 된다.

 

6) 문제에서 요구하는 것은, 산봉우리 x에 대한 intencity[x] 값들 중 최솟값과 그 때의 산봉우리이다.

따라서, 산봉우리 x에 대하여 (intencity[x], x)를 정렬하고, 가장 최솟값과 그 때의 x를 리턴하면 정답이다.

 

 

여담

이 문제... 2022년 KAKAO 여름 인턴십 문제이다... 어렵다 어려워~@

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<vector<ii>> graph(50005, vector<ii>(0));
vector<int> intencity(50005, INT_MAX);
priority_queue<ii, vector<ii>, greater<ii>> pq;


bool check(int a, int b, const vector<int>& gates, const vector<int>& summits) {
    
    if (find(summits.begin(), summits.end(), b) != summits.end()) return false;
    if (find(gates.begin(), gates.end(), a) != gates.end()) return false;
    return true;
}

void setGraph(const vector<vector<int>> paths, const vector<int>& gates, const vector<int>& summits) {
    
    for (auto v : paths) {
        int i = v[0];
        int j = v[1];
        int w = v[2];
        if (check(i, j, gates, summits)) graph[j].push_back({i, w});
        if (check(j, i, gates, summits)) graph[i].push_back({j, w});
    }
}

void Dijkstra(const vector<int>& gates) {
    
    for (auto x : gates) {
        intencity[x] = 0;
        pq.push({0, x});
    }
    
    while (!pq.empty()) {
        
        ii cur = pq.top(); //(intencity, 노드)
        pq.pop();
        
        if (intencity[cur.Y] != cur.X) continue;
        for (auto [next, w] : graph[cur.Y]) {
            if (max(intencity[cur.Y], w) < intencity[next]) {
                intencity[next] = max(intencity[cur.Y], w);
                pq.push({intencity[next], next});
            }
        }
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    
    setGraph(paths, gates, summits);
    Dijkstra(gates);
    
    vector<ii> v;
    for (auto x : summits) v.push_back({intencity[x], x});
    sort(v.begin(), v.end());
    
    return {v[0].Y, v[0].X};
}