[leetcode] 787 cheapest flight within stops (벨만포드)

문제설명

최대로 거칠 수 있는 노드의 수가 제한되어 상태에서 출발지부터 목적자까지 최단거리를 구한다. 

예를 들어  아래와 같은 그래프에서 

노드0에서 노드3까지 최대 1노드만 거쳐서 갈 수 있는 최단거리는 0->1->3 의 경로로 가는 700이 정답이다.

(0->1->2->3 으로 가면 400으로 더 적지만, 이는 두개의 노드를 거쳐야 한다)

 

문제풀이

밸만포드를 이용한다.

벨만포드는 음의 가중치가 있는 그래프에서 최단거리를 구할 수 있는 알고리즘인데, 다음과 같은 특징으로 이 문제에서 사용할 수 있다.

1. 노드 수 만큼 반복을 진행할 떄,  k번째 반복에서 k번째로 가까운 노드의 최단거리가 찾아짐이 보장된다.

2. k보다 더 멀리있는 노드에 대해서는 k개의 노드를 거쳐서 갈 수 있는 최단거리가 찾아짐이 보장된다.

3. 만약 k번으로 도달할 수 없는 노드가 있다면, 해당 노드까지의 거리는 무한대에서 변화되지 않는다.

 

다만 2,3을 만족시키기 위해서는 temp리스트를 사용해아 한다.

왜냐하면 노드수만큼 반복을 할 때 temp리스트를 사용하지않고 그 즉시 최단거리를 업데이트하면, k보다 더 멀리있는 노드가 k번 이하 반복에서 최단거리로 업데이트 될 수 있기 때문이다.

 

코드

class Solution {
        public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
            int[] distArray = new int[n];
            int INF = Integer.MAX_VALUE;
            Arrays.fill(distArray, INF);
            distArray[src]=0;

            int edgeSize = flights.length;

            for (int i=1; i<=k+1; i++) {
                int[] temp = Arrays.copyOf(distArray,n);
                for (int j=0; j<edgeSize; j++) {
                    int u = flights[j][0];
                    int v = flights[j][1];
                    int cost = flights[j][2];

                    if (distArray[u]!=INF && (distArray[u]+cost < temp[v])) {
                        temp[v] = distArray[u]+cost;
                    }
                }
                distArray = temp;

//                System.out.println(Arrays.toString(distArray));
            }

            if (distArray[dst]==INF) {
                return -1;
            } else{
                return distArray[dst];
            }
        }
    }