굉장히 좋은 문제를 풀었다. 그래프 문제를 연습하면서 느낀건데..난 진짜 하나도 모르는 바보였다. 다익스트라가 뭔지는 알아도 제대로 된 이론도 몰랐고.
벨만포드, 플로이드 등 너무 모르는 알고리즘이 많은거같다.
아래는 내가 처음 적었던 코드였는데 당연히 틀렸다. 왜 틀렸냐면 내가 DFS 를 사용하기도 하였고 문제가 의도 했던 최단 경로를 찾는 방법이랑 한참멀었다. DFS 과정으로 최단 경로를 찾는다는것은 계속 해서 노드의 거리를 업데이트 해줘야 하기때문에 매우 힘들다.
Priority_queue 를 사용한 방법도.. 예전에는 통과 했던 코드가 이번에 테스트 케이스가 추가되면서 TLE 가 걸렸다.
이 내용은 나중에 조금 더 자세하게 다룰 예정이지만.
최소 priority_queue 의 경우는 애초에 최소 값을 그대로 따라가기 때문에 조건문에 가중치 비교를 해줄 필요가 전혀 없다. 그저, 딱 목적지에 도착했을때가 최단 경로인거다
이 중요한걸 내가 모르고 있었다... ㅠㅠ 그런데 첫번째 시도에서는 fail 이 나왔다. 왜냐면 정말로 많은 테스트 케이스가 주어졌을때, 최소 가중치만 따라가다가 destination 에 도착을 못해서 TLE가 걸렸기 때문이다. 그렇기 때문에 통과된 코드에서는 한번 더 최적화가 걸려있었다.
마지막에 priority_queue 가 아닌 일번 큐로 했을때는 모든 테스트 케이스가 통과 되었다.
일반 queue를 사용하게 될 경우, 모든 노드를 큐에 집어 넣어서 모든 노드에서의 최소값을 구할 수 있다. 최적화는 안되어 있겠지만 당장 모든 노트를 집어 넣고 비교를 하기때문에 결국 destination 에 도착할 거고 TLE 가 안걸린다
이렇게 상황 마다 다르게 최적의 경로를 구할 수 있다는 문제가 있어서 정말 신기했다. 의미 있는 문제고 더 집중해서 풀어볼 생각이다.
class Solution {
public:
void dfs(int src, int dst, int k, int& step, int& currentPrice, vector<int>& nodeInfo, vector<vector<pair<int,int>>>& adj){
for(pair<int,int>& p : adj[src]){
int node = p.first, price = p.second;
int original = nodeInfo[node];
if(nodeInfo[node] > currentPrice + price && step <= k){
nodeInfo[node] = currentPrice + price;
dfs(node,dst,k,step+=1,currentPrice+=price,nodeInfo,adj);
step-=1;
currentPrice-=price;
}
}
}
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int,int>>> adj(n);
vector<int> nodeInfo(n,INT_MAX);
for(vector<int>& v : flights){
int from = v[0], to = v[1], price = v[2];
adj[from].push_back({to,price});
}
int currentPrice = 0;
int step = 0;
nodeInfo[src] = -1;
dfs(src,dst,k,step, currentPrice,nodeInfo,adj);
return nodeInfo[dst] == INT_MAX ? -1 : nodeInfo[dst];
}
};
priority_queue (fail)
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int,int>>> adj(n);
for(vector<int>& f: flights){
adj[f[0]].push_back({f[1],f[2]});
}
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> Q;
Q.push({0, src,k+1});
while(!Q.empty()){
vector<int> top = Q.top();
Q.pop();
int d = top[0];
int u = top[1];
int e = top[2];
if (dst == u) return d;
if (e > 0){
for(pair<int,int> & v: adj[u]){
Q.push({d+v.second, v.first, e-1});
}
}
}
return -1;
}
};
priority_queue (success)
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int, int>>> adj(n);
for (auto e : flights) {
adj[e[0]].push_back({e[1], e[2]});
}
vector<int> stops(n, numeric_limits<int>::max());
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
// {dist_from_src_node, node, number_of_stops_from_src_node}
pq.push({0, src, 0});
while (!pq.empty()) {
auto temp = pq.top();
pq.pop();
int dist = temp[0];
int node = temp[1];
int steps = temp[2];
// We have already encountered a path with a lower cost and fewer stops,
// or the number of stops exceeds the limit.
if (steps > stops[node] || steps > k + 1) continue;
if (node == dst) return dist;
for (auto& [neighbor, price] : adj[node]) {
pq.push({dist + price, neighbor, steps + 1});
}
}
return -1;
}
};
일반 queue(success)
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int,int>>>g(n);
for(auto& i:flights) g[i[0]].push_back({i[1],i[2]});
vector<int>dist(n,INT_MAX);
dist[src]=0;
queue<pair<int,int>>pq;
pq.push({0,src});
k+=1;
while(!pq.empty() && k--){
int n=pq.size();
while(n--){
int d=pq.front().first,s=pq.front().second;
pq.pop();
for(auto& i:g[s]){
if(dist[i.first]>d+i.second){
dist[i.first]=d+i.second;
pq.push({dist[i.first],i.first});
}
}
}
}
return dist[dst]==INT_MAX? -1:dist[dst];
}
};