[프로그래머스][C++] 등산코스 정하기
등산코스 정하기
문제 링크
분석
등산코스에서 출입구는 처음과 끝에 한번씩, 산봉우리는 한 번만 포함하는 경로 중 intensity가 최소인 경로를 찾는 문제입니다.
intensity는 경로 상에서 가장 큰 가중치를 의미합니다.
n은 지점으로, 노드의 개수를 의미합니다.paths는[i, j, w]형태로,i번 노드와j번 노드 사이에 가중치w인 간선을 의미합니다.gates는 출입구로 사용되는 노드들의 번호를 담은 배열입니다.summits는 산봉우리로 사용되는 노드들의 번호를 담은 배열입니다.
즉, 등산로를 그래프로 표현해야합니다.
intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최소값을 배열에 담아 반환해야합니다.
만약, intensity가 최소가 되는 등산코스가 여러개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택해야합니다.
최단 경로의 문제가 아니고, 최대 가중치를 최소화해야 합니다.
다익스트라 알고리즘을 변형해서 사용해볼 수 있습니다.
풀이
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <unordered_set>
using namespace std;
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
vector<int> answer(2);
// 인접 리스트 형태로 그래프 생성
vector<vector<pair<int, int>>> graph(n + 1);
for (const auto& path : paths)
{
int u = path[0], v = path[1], w = path[2];
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
// 산봉우리를 빠르게 확인하기 위해 unordered_set을 사용
unordered_set<int> summitSet(summits.begin(), summits.end());
// 각 노드까지의 최소 intensity를 저장
vector<int> intensity(n + 1, INT_MAX);
// 다익스트라를 위한 우선순위 큐
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
// 출입구 초기화
for (int gate : gates)
{
intensity[gate] = 0;
pq.emplace(0, gate);
}
// 다익스트라 탐색 시작
while (!pq.empty())
{
// 현재 노드와 해당 노드까지의 intensity
auto [CurrentIntensity, node] = pq.top();
pq.pop();
// 이미 더 낮은 intensity로 방문한 상태인 경우
if (CurrentIntensity > intensity[node])
{
continue;
}
// 산봉우리에 도달한 경우
if (summitSet.count(node))
{
continue;
}
// 인접 노드들을 탐색
for (const auto& [next, weight] : graph[node])
{
// 다음 노드까지의 intensity는 지금까지의 intensity와 현재 간선 가중치 중 더 큰 값
int newIntensity = max(CurrentIntensity, weight);
// 갱신이 가능한 경우에만 큐에 추가
if (newIntensity < intensity[next])
{
intensity[next] = newIntensity;
pq.push({newIntensity, next});
}
}
}
// 산봉우리 번호와 최소 intensity
answer[0] = 0;
answer[1] = INT_MAX;
// 번호가 가장 작은 산봉우리를 선택하기 위해 정렬
sort(summits.begin(), summits.end());
// 가장 적은 비용의 산봉우리 탐색
for (int summit : summits)
{
if (intensity[summit] < answer[1])
{
answer[0] = summit;
answer[1] = intensity[summit];
}
}
return answer;
}
산봉우리를 $O(1)$ 시간 복잡도로 확인하기 위해서 unordered_set을 사용합니다.
기존 다익스트라 알고리즘은 거리 합산을 하지만, 경로 상의 최대 가중치를 기준으로 탐색합니다.
우선순위 큐를 사용하여 intensity가 낮은 노드부터 탐색합니다.
성능 요약
시간 복잡도는 $O(m \ log \ n + s \ log \ s)$입니다.
- 인접 리스트 형태로 그래프를 생성하는 반복문 $O(m)$
m은 경로의 개수입니다.
- 다익스트라 알고리즘 $O(m \ log \ n)$
- 번호가 가장 작은 산봉우리를 선택하기 위한 정렬 $O(s \ log \ s)$
s는summits의 크기입니다.
- 가장 적은 비용의 산봉우리를 찾기 위한 반복문 $O(s)$
- $O(m) + O(m \ log \ n) + O(s \ log \ s) + O(s)$
공간 복잡도는 $O(n + m + s)$입니다.
- 인접 리스트로 표현한 그래프
vector<vector<pair<int, int>>>$O(m)$ intensity배열vector<int>$O(n)$- 다익스트라를 위한 우선순위 큐
priority_queue$O(m)$ - 산봉우리를 빠르게 확인하기 위한
unordered_set<int>$O(s)$ - $O(m) + O(n) + O(m) + O(s)$
테스트 성능
테스트 1 〉 통과 (0.01ms, 4.02MB)
테스트 2 〉 통과 (0.03ms, 4.18MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.13MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.03ms, 3.67MB)
테스트 7 〉 통과 (0.03ms, 4.21MB)
테스트 8 〉 통과 (0.03ms, 4.14MB)
테스트 9 〉 통과 (0.04ms, 4.19MB)
테스트 10 〉 통과 (0.06ms, 4.14MB)
테스트 11 〉 통과 (0.06ms, 4.2MB)
테스트 12 〉 통과 (0.09ms, 4.14MB)
테스트 13 〉 통과 (0.80ms, 4.48MB)
테스트 14 〉 통과 (3.51ms, 10.5MB)
테스트 15 〉 통과 (18.99ms, 49.3MB)
테스트 16 〉 통과 (21.49ms, 50.9MB)
테스트 17 〉 통과 (21.21ms, 50.9MB)
테스트 18 〉 통과 (1.98ms, 7.96MB)
테스트 19 〉 통과 (7.45ms, 21.9MB)
테스트 20 〉 통과 (26.03ms, 50.4MB)
테스트 21 〉 통과 (36.28ms, 40.3MB)
테스트 22 〉 통과 (2.77ms, 6.18MB)
테스트 23 〉 통과 (15.02ms, 16.9MB)
테스트 24 〉 통과 (12.13ms, 13.7MB)
테스트 25 〉 통과 (53.46ms, 53.4MB)
댓글남기기