(Leet Code JS)Cheapest Flights Within K stops

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

Cheapest Flights Within K Stops - LeetCode

다익스트라 알고리즘 활용.

 

우선 graph라는 이름의 n 크기의 배열을 선언하여 []로 초기화.

또한, n 크기의 dist 배열도 선언하여 infinity로 초기화.

 

flights를 순회하여 그래프를 그려준다.

단방향이기 때문에 from, to, price만 저장하면 된다.

 

시작은 src부터기 때문에

큐에 [시작지점, 현재 cost, 현재 멈춤 횟수]인 [src, 0, 0]을 넣어 시작한다.

또한, dist[src] = 0으로 갱신.

 

queue가 빌 때까지 반복한다.

현재 맨 앞에 있는 수를 꺼내어 각각

[current, cost, stop]으로 저장한다.

 

현재 있는 위치에서 갈 수 있는 지점까지 for문을 이용해 찾는다.

다음 지점과 다음 지점까지 가는데 걸리는 비용을 [next, price]로 저장.

현재 지점 ~ 다음 지점까지 걸리는 비용 = cost + price = nextCost로 저장.

 

if문을 통해 조건 검사를 하여 dist[next]를 갱신한다.

dist[next] > nextCost 라면 갱신 조건이다.

여기서 또 다른 조건이 붙는다.

바로 멈춤 횟수다.

현재 멈춤 횟수(stop)가 k 보다 작거나 같다면 dist[next]를 갱신하고, queue에 다음 지점을 넣어주면 된다.

 

var findCheapestPrice = function(n, flights, src, dst, k) {
    const graph = Array.from({length: n}, () => []);
    const dist = Array(n).fill(Infinity);
    const queue = [];
    
    for(let i = 0; i < flights.length; i++){
        const [from, to, price] = flights[i];
        
        graph[from].push([to, price]);
    }
    
    queue.push([src, 0, 0]);
    dist[src] = 0;
    
    while(queue.length){
        const [current, cost, stop] = queue.shift();
        
        for(let i = 0; i < graph[current].length; i++){
            const [next, price] = graph[current][i];
            const nextCost = cost + price;
            
            if(dist[next] > nextCost && stop <= k){
                dist[next] = nextCost;
                queue.push([next, nextCost, stop + 1]);
            }
        }
    }
    
    return dist[dst] === Infinity ? -1 : dist[dst];
};