[LeetCode] Path with Maximum Probability 🧮 (Java)

🧩 문제 파악

• 방향 가중치 그래프가 주어진다.
• start_node에서 end_node로 가는 경로 중 성공 확률이 최대가 되는 경로의 확률을 구하는 문제.
• 간선의 가중치는 0과 1사이의 확률값.
• 경로가 없으면 0.0 반환
• 확률의 합이 아니라 곱을 구해야 함!

🎯 접근 방법

그래프 표현 : 인접리스트

• Map<Integer, List<Edge>> graph를 사용하여 인접 리스트 형태로 표현.
• graph.get(u).add(new Edge(v, w)) , graph.get(v).add(newEdge(u, w))로 양방향 그래프를 구성한다.
• Edge 클래스는 node 와 prob를 저장한다.

다익스트라를 사용해 최대 확률 경로 구하기

• “곱의 값이 최대가 되는 경로”를 구해야 하므로, 확률의 곱이 큰 경로부터 우선적으로 탐색.
• 우선순위 큐를 내림차순으로 구성 → 확률이 큰 것부터 꺼낼 수 있음.

  Queue<Edge> pq = new PriorityQueue<>((a, b) -> Double.compare(b.prob, a.prob));

거리 배열 초기화

• dist[node]는 start_node에서 node로 갈 수 있는 가장 높은 확률을 저장.
• 처음에는 Arrays.fill(dist, 0)으로 초기화.
• start_node의 확률은 1로 설정하여 시작.

다익스트라 반복 처리

• 우선 순위 큐에서 현재 노드 curr를 꺼내서, 해당 노드의 인접 노드를을 순회한다.
  • 현재 노드까지의 확률 dist[curr.node]과 현재 간선의 확를 next.prob을 곱해
  • 해당 노드까지의 새로운 확률 nextDist를 구한다.
• 만약 dist[next.node] < nextDist이라면,
  • 더 높은 확률 경로를 찾은 것이므로, 갱신하고 pq에 삽입하여 다음 탐색을 예약한다.
• 이 과정을 통해 확률의 곱이 가장 높은 경로부터 탐색하고, 최종적으로 가장 높은 확률을 구할 수 있다!

최종 반환

• dist[end_node]가 start_node에서 end_node까지 도달할 수 있는 가장 높은 확률이므로, 이를 반환한다.
• 경로가 없으면 dist[end_node]는 여전히 0이므로, 문제 조건에 맞게 0.0을 반환하게 된다.

🌟 코드 구현

class Solution {

    // 간선(Edge) 클래스: 연결된 노드 번호와 해당 간선의 성공 확률을 가짐
    class Edge {
        int node;       // 연결된 노드 번호
        double prob;    // 성공 확률

        Edge(int node, double prob) {
            this.node = node;
            this.prob = prob;
        }
    }

    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        // 그래프 인접 리스트 생성
        Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>()); // 노드별 인접 리스트 초기화
        }

        // 간선 정보를 기반으로 그래프 구축 (무방향)
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];     // 출발 노드
            int v = edges[i][1];     // 도착 노드
            double w = succProb[i];  // 성공 확률

            // 양방향 간선 추가
            graph.get(u).add(new Edge(v, w));
            graph.get(v).add(new Edge(u, w));
        }

        // 확률 배열 (dist): start_node에서 각 노드까지의 최대 확률 저장
        double[] dist = new double[n];
        Arrays.fill(dist, 0); // 초기값: 0

        // 우선순위 큐 (확률이 큰 노드부터 꺼내도록 내림차순 설정)
        Queue<Edge> pq = new PriorityQueue<>((a, b) -> Double.compare(b.prob, a.prob));

        // start_node에서 시작, 확률은 1
        pq.offer(new Edge(start_node, 1));
        dist[start_node] = 1;

        // 다익스트라 알고리즘
        while (!pq.isEmpty()) {
            Edge curr = pq.poll(); // 현재 노드와 현재까지의 확률 가져오기

            // 현재 노드와 연결된 모든 노드를 확인
            for (Edge next : graph.get(curr.node)) {
                double nextDist = dist[curr.node] * next.prob; // 현재 확률 * 간선 확률 = 다음 노드로 가는 새로운 확률

                // 더 높은 확률 경로를 발견하면 갱신
                if (dist[next.node] < nextDist) {
                    pq.add(new Edge(next.node, nextDist)); // 다음 방문 예약
                    dist[next.node] = nextDist;            // 확률 갱신
                }
            }
        }

        // end_node까지의 최대 확률 반환
        return dist[end_node];
    }
}