문제
Input:
n = 5
edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]
time = 3
change = 5
Output:
13
요약:
인접 노드로 건너갈 때 time의 시간이 걸리고 매 change마다 신호가 바뀌어 움직일 수 없다
각 노드는 change로 변한 신호가 초록불일때만 움직일 수 있고 빨간불일때만 대기할 수 있다
노드 1에서부터 n까지의 2번째 최소 거리 비용을 구하라
조건:
2 <= n <= 10^4
n - 1 <= edges.length <= min(2 * 10^4, n * (n - 1) / 2)
edges[i].length == 2
1 <= ui, vi <= n
ui != vi
중복되는 간선은 존재하지 않는다
모든 노드는 직접 혹은 간접적으로라도 서로 도달할 수 있다
1 <= time, change <= 10^3
형식:
class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
}
};
풀이 과정
설명:
먼저, dijkstra알고리즘을 사용하기 위한 그래프를 만들어야 한다
n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2) 를 보면 n을 통해 간선의 개수를 구하는 조건이 있다
이 조건은 n을 기준으로 간선의 개수를 정하는데 이를 통해 n값을 유추하여 n == node의 개수로 볼 수 있다
n을 기준으로 빈 그래프를 생성해 줄 수 있겠다.
또한 각 노드의 비용은 time으로 통일 되었으니 비용을 그래프에 담을 필요도 없고 n * n 보다는 빈 벡터를 생성하여 push_back을 해주는 것이 공간을 효율적으로 사용할 수 있을 것이다
vector<vector<int>> graph(n) 으로 선언하면 되겠다
양방향 그래프이므로 우하향 대칭으로 값을 넣어 그래프를 완성시켜주고 dijkstra 알고리즘을 돌린다
dijkstra 알고리즘을 돌리는 가장 첫번째 고난은 change라고 볼 수 있는데, 우리는 홀수와 짝수를 통해 time과 change 간에 신호가 빨간불인지 초록불인지 구별을 할 수 있다.
change * 홀수 <= time < change * 짝수라는 조건에서는 빨간불임을 확실히 알 수 있다
즉 time / change를 통해 몫이 홀수면 빨간불로 change - time % change값 만큼 추가로 대기를 하면 된다
자, 이제 우리가 할 일은 time을 계속 증가시키며 time과 change의 상관관계에 따라 비용이 달라지는 node들을 priority_queue에 계속 넣어가며 최소 비용을 찾으면 된다!
여기서 마지막으로 추가 조건이 있는데, 바로 두번째로 최소 비용거리를 구해야 한다는 것이다
이는 단순하게 처음에 반환할 비용값을 0으로 두고 목적지를 찾았을때 비용이 0이면 업데이트 해주고 비용에 값이 들어와 있으면 두번째로 찾은 경로이기 때문에 해당 비용을 반환하기로 했다
시간복잡도:
그래프를 만들면서 edges 탐색에 E
거기에 다익스트라의 기본 시간 복잡도인 Θ( |E| + |V| log |V| )
E + Θ( |E| + |V| log |V|)
...
코드:
class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
// n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2) 라는 조건으로
// n == node 개수임을 알 수 있다
// 매번 i - 1 하기에는 코드가 복잡해질것 같아 그냥 + 1 함
vector<vector<int>> graph(n + 1);
for (int i = 0; i < edges.size(); ++i) {
// 양방향 그래프 이므로 양쪽에 값을 넣어줌
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
return dijkstra(graph, edges, time, change);
}
private:
int dijkstra(vector<vector<int>>& graph,
vector<vector<int>> &edges,
int time,
int change)
{
int secMinTime = 0;
int destination = graph.size() - 1;
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>>
priorityQueue;
priorityQueue.push({0, 1});
while (!priorityQueue.empty()) {
// auto [currentTime, currentNode] = priorityQueue.top();
// by c++ 17
int currentTime = priorityQueue.top().first;
int currentNode = priorityQueue.top().second;
priorityQueue.pop();
// 목적지 도착
if (currentNode == destination) {
if (secMinTime)
return currentTime;
else
secMinTime = currentTime;
}
for (int i = 0; i < graph[currentNode].size(); ++i) {
if (graph[currentNode][i]) {
int signal = currentTime / change;
// 신호에 따른 time 증가
if (signal && signal % 2) {
priorityQueue.push({
currentTime + time + change - (currentTime % change), graph[currentNode][i]});
}
else {
priorityQueue.push({
currentTime + time, graph[currentNode][i]});
}
}
}
}
return 0;
}
};
풀이 결과
틀렸다 뭐가 문제인지 모르겠다...
너무 오랫동안 붙잡아서 그냥 패스해야겠다...
그래도 다익스트라를 구현하는데 성공해서 꽤 큰 의의를 지닌 하루였다