Cheapest Flights Within K Stops

https://leetcode.com/problems/cheapest-flights-within-k-stops/

Cheapest Flights Within K Stops - LeetCode

 

정해진 경유지 수 이내에서 목적지까지 가장 적은 비용으로 도달하는 방법을 찾는 문제이다.
목적지까지 최단 비용 문제의 경우 다익스트라 알고리즘을 이용해줄 수 있다.

 

해당 문제 또한 다익스트라 알고리즘으로 해결할 수 있으며, 특이점으로는 경유지 숫자에 제한이 있다는 점이다. 따라서 PriorityQueue를 이용하여 경로를 설정할 때 경유지 개수를 포함 시켜 문제를 해결하였다.

public class Solution {  
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {  
        List<Route>[] prices = new ArrayList[n];  
        for(int i = 0; i < n; i++){  
            prices[i] = new ArrayList<>();  
        }  
  
        PriorityQueue<Route> pq = new PriorityQueue<>((a, b) -> {  
            if(a.stop == b.stop){  
                return a.price - b.price;  
            }  
            return a.stop - b.stop;  
        });  
  
        for(int[] flight: flights){  
            int from = flight[0];  
            int to = flight[1];  
            int price = flight[2];  
  
            prices[from].add(new Route(to, price, 0));  
        }  
  
        for(Route route: prices[src]){  
            pq.add(route);  
        }  
  
        int[] minValue = new int[n];  
        Arrays.fill(minValue, Integer.MAX_VALUE);  
        while(!pq.isEmpty()){  
            Route now = pq.poll();  
            int to = now.to;  
            int price = now.price;  
            int stop = now.stop;  
            if(k < stop){  
                continue;  
            }  
  
            if(minValue[to] < price){  
                continue;  
            }  
  
            minValue[to] = price;  
  
            for(Route next: prices[to]){  
                int nextTo = next.to;  
                int nextPrice = price + next.price;  
                int nextStop = stop + 1;  
                if(minValue[nextTo] > nextPrice){  
                    pq.add(new Route(nextTo, nextPrice, nextStop));  
                }  
            }  
        }  
  
        return minValue[dst] == Integer.MAX_VALUE ? -1 : minValue[dst];  
    }  
  
    private class Route{  
        int to;  
        int price;  
        int stop;  
  
        Route(int to, int price, int stop){  
            this.to = to;  
            this.price = price;  
            this.stop = stop;  
        }  
    }  
}