[LeetCode/Java] Path with Maximum Probability

문제

---

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

문제 파악

---

• start 부터 end 까지 가는 동안에 각 cost를 곱해서 최대가 되는 cost를 구하는 문제
• 만약 갈 수 있는 길이 없으면 0 을 리턴

접근 방법

---

• 다익스트라, 우선순위 큐(최대값을 우선)
• 양방향 그래프
• 최대값으로 갱신을 위해 dist배열의 초기화 값은 0
• 각 노드에 갈때까지 최대 확률을 저장할 수 있도록 갱신

코드 구현

import java.util.*;

class Solution {
    static List<Node>[] graph;
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        graph = new ArrayList[n];

        for(int i = 0; i < n; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < edges.length; i++){
            graph[edges[i][0]].add(new Node(edges[i][1], succProb[i]));
            graph[edges[i][1]].add(new Node(edges[i][0], succProb[i]));
        }

        double[] answer = dijkstra(n, start_node);
        return answer[end_node];
    }
    static double[] dijkstra(int n, int start){
        PriorityQueue<Node> pq = new PriorityQueue<>((e1, e2) -> Double.compare(e2.cost, e1.cost));
        double[] dist = new double[n];

        Arrays.fill(dist, 0);
        dist[start] = 1; // 본인의 노드로 갈 확률은 1 
        pq.add(new Node(start, 1.0));  // 시작 노드를 큐에 추가

        while(!pq.isEmpty()){
            Node current = pq.poll();
            int nexts = current.v;
            double currentCost = current.cost;
            if(currentCost < dist[nexts]) continue;

            for(Node next : graph[nexts]){
                int v = next.v;
                double weight = next.cost;

                if(dist[v] < currentCost * weight){
                    dist[v] = currentCost * weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        System.out.println(Arrays.toString(dist));
        return dist;
    }
    static class Node{
        int v;
        double cost;
        Node(int v, double cost){
            this.v = v;
            this.cost = cost;
        }
    }
}

배우게 된 점

---

• PriorityQueue의 정렬 기준
  • PriorityQueue는 기본적으로 오름차순으로 정렬
  • Double.compare(e2.cost, e1.cost)을 사용하여 내림차순으로 정렬되도록 함
  • e2.cost가 e1.cost보다 크면 e2가 더 높은 우선순위를 가지게 됩니다.
• Double.compare 메서드의 반환 값
  • Double.compare(d1, d2)는 d1이 d2보다 작으면 음수를, d1이 d2와 같으면 0을, d1이 d2보다 크면 양수를 반환
  • Double.compare(e2.cost, e1.cost)는 e2.cost가 e1.cost보다 클 때 양수를 반환하므로, e2가 우선순위가 더 높다는 것을 의미