[LeetCode] 787번 Cheapest Flights Within K Stops 문제를 풀어보았다. (ft. java)

2023년 01월 26일 목요일 - 눈이 펑펑 와요

오늘 올려볼 문제는 787번 Cheapest Flights Within K Stops 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘 문제 미디엄치고는 어려웠어요...

입력

사진에서도 볼 수 있듯이 int 값 4개와 2차원 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

방향 그래프가 주어지고 최대 들를 수 있는 경유지 개수가 주어졌을 때 목적지로 갈 수 있는 방법 중 가장 짧은 길이를 구하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

bfs 를 사용하는데 dp를 섞어서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        HashMap<Integer, Integer>[] arr = new HashMap[n];
        var v = new int[n];
        int result = Integer.MAX_VALUE;
        
        Arrays.fill(v, Integer.MAX_VALUE);
        
        for(var f : flights) {
            if(arr[f[0]] == null) arr[f[0]] = new HashMap<>();
            
            arr[f[0]].put(f[1], f[2]);
        }
        
        var q = new LinkedList<int[]>();
        q.add(new int[]{src, 0});
        
        for(int i = 0; i <= k + 1; i++) {
            int size = q.size();
            for(int j = 0; j < size; j++) {
                var now = q.poll();
                
                if(now[1] > result || v[now[0]] < now[1]) continue;
                if(now[0] == dst) {
                    result = Math.min(result, now[1]);
                    continue;
                }
                if(arr[now[0]] == null) continue;
                
                v[now[0]] = now[1];
                
                for(var key: arr[now[0]].keySet()) q.add(new int[] {key, arr[now[0]].get(key) + now[1]});
            }
        }
        
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}

---

제출 화면

오늘 오랜만에 출근해서 그런지 힘드러따...

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.