[LeetCode#787] Cheapest Flights Within K Stops

❒ Description

---

제목	Cheapest Flights Within K Stops
링크	https://leetcode.com/problems/cheapest-flights-within-k-stops/description/
자료구조	비선형 (그래프) - 최단거리
시간 복잡도	O(ElogV)

다익스트라 알고리즘을 사용해서 풀 수 있는 문제이며, Comparable 인터페이스도 활용할 수 있다.
이 문제는 경유 횟수가 제한되어 있어서 굉장히 까다로웠다.

 

 

 

 

 

❒ Solution

---

1.  단순 solve

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    //1. filghts 배열을 통해 graph 생성
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] flight : flight) {
    	int departure = flight[0];
        int arrival = flight[1];
        int price = flight[2];
        graph.get(departure).add(new int[]{arrival, price});
    }
    
    //2. 방문 여부와 경유 횟수를 관리하기 윈한 Map 생성 
    Map<Integer, Integer> managingFlights = new HashMap<>();
    
    //3. 큐 생성 및 최초 값 삽입 (도착지, 비용, 경유횟수)
    Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p[1]));
    pq.add(new int[]{src, 0, 0});
    
    //4. 큐가 빌 때 까지 반복
    while (!pq.isEmpty()) {
        int[] cheapest = pq.poll();
        int arrival = cheapest[0], price = cheapest[1], viaCount = cheapest[2];
        
        // 반복하는 과정에서 현재 노드와 dst와 일치한다면 결과 반환
        if (arrival == dst) {
            return price;
        }
        
        // 5. 방문 처리
        visited.put(arrival, viaCount);
        
        // 6. 경유를 더 할 수 있다면, 
        if (viaCount < k) {
            viaCount += 1;
            // 7. 현재 노드에서 출발하는 모든 항공권 탐색하며 처리
            for (int[] node : graph.get(arrival)) {
                int nextNode = node[0];
                int nextPrice = node[1];
                if (!visited.containsKey(nextNode) || viaCount < visited.get(nextNode)) {
                    int totalPrice = price + nextPrice;
                    pq.add(new int[] {nextNode, totalPrice, viaCount});
                }
            }
        }
    }
    return -1;
}

 

 

!visited.containsKey(nextNode)

• 처음 방문하는 노드라면 더 나은 경로가 없으므로 탐색을 계속한다.

 

viaCount < visited.get(nextNode)

• visited.get(nextNode)는 해당 노드에 도달할 때 사용된 경유 횟수를 의미
• viaCount는 현재 경로에서 nextNode에 도달할 때의 경유 횟수를 의미
• viaCount가 이전에 기록했던 경유 횟수보다 적다면, 더 적은 경유로 해당 노드에 도달할 수 있다는 것을 의미
• 만약 경유 횟수가 이전보다 크거나 같으면, 이미 더 나은 경로를 찾았기 때문에 굳이 다시 탐색할 필요X

 

 

 

2. Comparable 활용한 풀이

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    //1. graph 생성
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] flight : flights) {
        int idx = flight[0];
        int to = flight[1];
        int price = flight[2];
        graph.get(idx).add(new int[] {to, price});
    }
    //2. 가격이 낮은 순으로 하는 PQ 생성 & 진입점 삽입
    Queue<Flight> pq = new PriorityQueue<>();
    pq.add(new Flight(src, 0, 0));
    //3. 방문과 경유횟수를 관리해주는 맵 생성
    Map<Integer, Integer> visited = new HashMap<>();
    //4. PQ가 빌 때 까지 반복 수행
    while (!pq.isEmpty()) {
        Flight flight = pq.poll();
        int node = flight.departure, price = flight.price, viaCount = flight.viaCount;
        // ※ 만약 현재 노드가 최종 도착지라면 이때의 가격을 반환
        if (node == dst) {
            return price;
        }
        //5. 현재 노드를 방문 처리 (노드, 경유횟수)
        visited.put(node, viaCount);
        //6. 경유횟수 검증
        if (viaCount <= k) {
            //7. 경유횟수 1 증가
            viaCount += 1;
            //8. arrival을 출발지로 하는 경로가 있다면 처리
            for (int[] v : graph.get(node)) {
                int nextNode = v[0];
                int noextPrice = v[1];
                //9. 다음 노드를 최초로 방문하거나, 이전에 기록했던 경유 횟수보다 적을 경우  
                if (!visited.containsKey(nextNode) || viaCount < visited.get(nextNode)) {
                    int totalPrice = price + nextPrice;
                    pq.add(new Flight(nextNode, totalPrice, viaCount));
                }
            }
        }
    }
    return -1;
}

public static class Flight implements Comparable<Flight> {
    int departure;
    int price;
    int viaCount;

    public Flight(int departure, int price, int viaCount) {
        this.departure = departure;
        this.price = price;
        this.viaCount = viaCount;
    }

    @Override
    public int compareTo(Flight o) {
        return Integer.compare(this.price, o.price);
    }
}

 

 

 

 

 

---