[알고리즘] Leetcode_787_Cheapest_Flights_Within_K_Stops

Problem

Solve

그 이전에 풀었던 Leetcode_743_Network_Delay_Time 의 최단 경로 구하는 다익스트라 알고리즘을 사용하는 것에 환승조건이 추가된 것이다.
매커니즘은 비슷하게 작동하게 해놓고 환승조건 k 이하로 최단경로를 찾는 것이라 while 문에 k 에 대한 조건을 냈다.

`class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Map<Integer, List<int[]>> graph = new HashMap<>(); // 도시와 그에 연결된 비행 정보를 저장할 Map
        for (int[] flight : flights) {
            int from = flight[0];
            int to = flight[1];
            int price = flight[2];
            if (!graph.containsKey(from)) {
                graph.put(from, new ArrayList<>());
            }
            graph.get(from).add(new int[]{to, price});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // 최소 힙을 이용한 우선순위 큐
        pq.offer(new int[]{0, src, K + 1}); // 비용, 출발 도시, 남은 허용 비용 횟수를 저장하는 배열을 우선순위 큐에 삽입
        int[] cost = new int[n]; // 각 도시까지의 최소 비용을 저장할 배열
        Arrays.fill(cost, Integer.MAX_VALUE); // 초기값은 무한대로 설정
        cost[src] = 0; // 출발 도시의 비용은 0

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int curCost = cur[0];
            int curCity = cur[1];
            int remainingStops = cur[2];

            if (curCity == dst) { // 목적지에 도착한 경우 최소 비용 반환
                return curCost;
            }

            if (remainingStops > 0) { // 남은 허용 비용 횟수가 0보다 큰 경우에만 탐색 수행
                if (graph.containsKey(curCity)) { // 현재 도시에서 출발하는 비행 정보가 있는 경우
                    for (int[] flight : graph.get(curCity)) {
                        int nextCity = flight[0];
                        int nextCost = curCost + flight[1];
                        if (nextCost < cost[nextCity]) { // 현재 비용이 저장된 비용보다 작은 경우에만 갱신
                            cost[nextCity] = nextCost;
                            pq.offer(new int[]{nextCost, nextCity, remainingStops - 1});
                        }
                    }
                }
            }
        }

        return -1; // 목적지에 도착하지 못한 경우 -1 반환
    }
}

그치만 테스트 케이스 52개 중 46개만 통과가 되었었다.

이 테스트 케이스에서는 src = 0 -> dst = 2 까지 갈 수 있는 경로는
① 0 -> 1 -> 2 = 5 + 5 = 10
② 0 -> 1 -> 4 -> 2 = 5 + 1 + 1 = 7
③ 0 -> 3 -> 1 -> 2 = 2 + 2 + 5 = 9
④ 0 -> 3 -> 1 -> 4 -> 2 = 2 + 2 + 1 + 1 = 6
라는 다섯가지 경우의 수가 있다.

만약 환승조건 없는 그냥 다익스트라 알고리즘을 통한 최단경로는 ④ 6 이 될 것이다.
하지만 위의 코드로는 ③ 9 가 나와버렸다.

④ 의 조건에서는 환승조건에 의해 걸러졌고 ③ 이 아닌 ② 가 출력이 나오는 이유가 뭘까 생각을 해보다 0 -> 1 까지는 0 -> 1 = 5 보다 작은 0 -> 3 -> 1 = 2 + 2 = 4 가 되어버려 1 -> 2 가는 경로는 5보다 작은 4에서 5을 추가해버리는 경우가 발생해버렸다.
즉, 우선순위큐에서 불러와버리는 0 에서의 거리는 바로바로 갱신되는 작은 값으로만 갱신된다는 것이다.

이로써 환승횟수에 따라서 cost 는 변경되지 말아야 한다. 말로 설명하기 어렵지만 그림으로 설명해보겠다.

여기서는 cost 와 temp로 나누는데 이는 환승단계에 있어서 겹치지 않게 하기 위함이다. cost는 각 항공권 정보를 순회할 때 마다 갱신된 temp 를 복사하고 temp 는 전 환승단계에서 마무리된 cost 값에 따라 환승이 진행이 된다.

class Solution{
	 public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

        int[] cost = new int[n]; // 각 도시까지의 최소 비용을 저장할 배열
        Arrays.fill(cost, Integer.MAX_VALUE); // 초기값은 무한대로 설정
        cost[src] = 0; // 출발 도시의 비용은 0

        for (int i = 0; i <= K; i++) { // 최대 비용 허용치 K까지 반복
            int[] temp = Arrays.copyOf(cost, n); 
            // 이전 단계의 비용을 저장할 임시 배열
            //Arrays.copyOf(original, newLength)  복사할 원본 배열 original 배열의 크기 newLength
            //newLength 가 원본 배열의 길이보다 작은 경우 지정된 길이까지 , 혹은 클 경우 뒷부분은 0 또는 null로

            for (int[] flight : flights) {
                int from = flight[0];
                int to = flight[1];
                int price = flight[2];
               
                if (cost[from] != Integer.MAX_VALUE) { // 출발 도시까지의 비용이 무한대가 아닌 경우에만 갱신 , 무한대인 경우는 아직 경우하지 않았음을 의미
                    temp[to] = Math.min(temp[to], cost[from] + price); // 이전 단계의 비용과 현재 비용을 비교하여 갱신
                }
            }
            cost = temp; // 현재 단계의 비용을 저장

        }
        return cost[dst] == Integer.MAX_VALUE ? -1 : cost[dst]; // 목적지의 비용이 무한대인 경우 -1 반환, 그렇지 않으면 목적지의 비용 반환
    }
}

여기서 중요한 점은 환승횟수 k만큼 만 flights 정보만을 순회한다는 것이다.

아직 처음 코드에서 말로 설명할 수 있는 오류는 찾았지만 아직까지 코드를 완벽하게 고치지는 못했다. 이는 더 진행해보고 수정하도록 하겠다.