(Leet Code JS)Path With Maximum Probability

https://leetcode.com/problems/path-with-maximum-probability/

Path with Maximum Probability - LeetCode

다익스트라 알고리즘.

 

start에서 end까지 갈 수 있는 확률 중 가장 높은 path를 찾아야 한다.

일반적인 다익스트라처럼 큐를 이용.

 

우선 n 크기의 배열을 선언하고, 빈 배열로 초기화 하여 graph라는 이름으로 선언.

각 지점까지의 거리를 나타내는 dist 배열을 n 크기로 선언하고, -Infinity로 초기화.

큐 또한 빈 배열로 선언한다.

 

다음은 edges를 순회하면서 그래프를 그려주도록 한다.

양방향이기 때문에 from과 to 인덱스에 push한다.

 

시작은 start에서 시작이고, 확률은 1이다.

dist[start] = 1로 갱신.

 

while로 queue가 빌 때까지 반복.

현재 노드를 큐의 앞에서 꺼내온다.

for문으로 현재 노드에서 갈 수 있는 노드들을 순회.

갈 수 있는 노드는 [next, nextP]로 가져오고, 갈 수 있는 확률은 현재 확률 * 다음 노드의 확률이다.

(nextProb = p * nextP)

 

이제 dist[next]와 nextProb을 비교하여 더 높은 값을 dist[next]에 갱신하고, 큐에 다음 노드를 넣어주면 된다.

리턴값은 dist[end]가 -Infinity인지 확인하고, 0 아니면 dist[end]를 리턴한다.

var maxProbability = function(n, edges, succProb, start, end) {
    const graph = Array.from({length: n}, () => []);
    const dist = Array(n).fill(-Infinity);
    const queue = [];
    
    for(let i = 0; i < edges.length; i++){
        const [from, to] = edges[i];
        const p = succProb[i];
        
        graph[from].push([to, p]);
        graph[to].push([from, p]);
    }
    
    queue.push([start, 1]);
    dist[start] = 1;
    
    while(queue.length){
        const [current, p] = queue.shift();
        
        for(let i = 0; i < graph[current].length; i++){
            const [next, nextP] = graph[current][i];
            const nextProb = p * nextP;
            
            if(dist[next] < nextProb){
                dist[next] = nextProb;
                queue.push([next, nextProb]);
            }
        }
    }
    
    return dist[end] === -Infinity ? 0 : dist[end];
};