[Java] leetcode 787. Cheapest Flights Within K Stops

문제

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

Cheapest Flights Within K Stops - LeetCode

최대 k +1 번 움직였을 때 src 부터 dst 까지 최단 거리 구하는 문제

경로가 없으면 -1 리턴.

알아야 할 개념

• BFS 레벨탐색
• 인접 리스트

풀이

로직은 다음과 같다. 

1. 주어진 정점에 대해 인접 리스트 그래프를 구현한다. 
2. BFS 레벨 탐색을 진행한다. 
3. 현재 레벨이 k + 1 을 초과하면 레벨 탐색을 종료하고 dist[ src ] 의 값을 리턴한다. 

큐를 사용한 BFS 로 풀이 하였다. 

큐에는 [ 방문할 정점, 현재 정점까지의 거리 ] 를 삽입한다. 처음에는 [src, 0 ] 을 넣어주고, 

1. 큐에서 모든 원소를 다 빠질 떄까지

2. 레벨이 k + 1 이하 일 떄까지 탐색을 진행한다. 

Q.offer(new int[]{src,0});

 

while 문을 걸어주어 큐에 있는 원소를 탐색한다.

        while(!Q.isEmpty() && level < k+1){
            int size = Q.size();
            for(int i =0 ;i < size;i ++){
                int cur[] = Q.poll();//현재 정점 정보를 하나 꺼낸다. 
                for(int next[] : list.get(cur[0])){//현재 정점에 연결된 인접 리스트를 꺼낸다. 
                    if(cur[1] + next[1] < v[next[0]]){//최단 거리 업데이트 될 때만 큐에 정점 삽입
                        v[next[0]] = cur[1] +next[1];
                        Q.offer(new int[]{next[0], v[next[0]]});
                    }
                }
            }
            level++;//레벨 증가
        }

코드

자바

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<List<int[]>> list = new ArrayList<>();
        for(int i =0 ;i < n; i++)
            list.add(new ArrayList<>());
        
        for(int x[] : flights){
            list.get(x[0]).add(new int[]{x[1],x[2]});
        }
        
        Queue<int[]> Q =new LinkedList<>();
        if(src == dst)return 0;
        int[] v = new int[n];
        Arrays.fill(v,Integer.MAX_VALUE);
        v[src] = 0;
        Q.offer(new int[]{src,0});
        int level=0;
        while(!Q.isEmpty() && level < k+1){
            int size = Q.size();
            for(int i =0 ;i < size;i ++){
                int cur[] = Q.poll();
                for(int next[] : list.get(cur[0])){
                    if(cur[1] + next[1] < v[next[0]]){
                        v[next[0]] = cur[1] +next[1];
                        Q.offer(new int[]{next[0], v[next[0]]});
                    }
                }
            }
            level++;
        }
        return v[dst] == Integer.MAX_VALUE ? -1 : v[dst];
    }
}