[LeetCode] 1514. Path with Maximum Probability (java)

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

 

 

문제 파악

• 주어진 정보/입력값
  • n개의 노드를 가진 무방향 그래프 edges이 주어진다.
  • edges[i] = [a, b]가 주어져 a와 b를 연결하는 무방향 간선이 표현될 때, 해당 간선을 순회하는 성공 가능성을 가리키는 succProb[i]이 같이 주어진다.
• 해결해야 할 문제 
  • start 노드와 end 노드가 주어질 때, start에서 end로 가는 길 중 가장 높은 가능성을 가진 길을 찾아내어 그 성공 가능성을 return하라.
  • 만약, start에서 end로 가는 길이 없다면, 0을 return하라.
  • 소숫점 다섯번째 자리까지 return하라.

 

문제 풀이

Dijkstra

package main.java.LeetCode;

import java.util.*;

class PathWithMaximumProbability {

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        // 그래프 변환
        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++) {
            graph.get(edges[i][0]).add(new Edge(edges[i][1], succProb[i]));
            graph.get(edges[i][1]).add(new Edge(edges[i][0], succProb[i]));
        }

        double[] maxProbability = new double[n];

        Queue<Entry> pq = new PriorityQueue<>();
        pq.add(new Entry(start, 1));
        maxProbability[start] = 1;

        while (!pq.isEmpty()) {
            Entry curr = pq.remove();
            if (curr.maxProbability < maxProbability[curr.node])
                continue;

            List<Edge> edgeList = graph.get(curr.node);
            if (edgeList != null) {
                for (Edge edge : edgeList) {
                    double newProbability = curr.maxProbability * edge.probability;
                    if (newProbability > maxProbability[edge.to]) {
                        pq.add(new Entry(edge.to, newProbability));
                        maxProbability[edge.to] = newProbability;
                    }
                }
            }

        }

        if (maxProbability[end] == 0)
            return 0;
        else
            return maxProbability[end];
    }

    class Edge {
        int to;
        double probability;

        Edge(int to, double probability) {
            this.to = to;
            this.probability = probability;
        }
    }

    class Entry implements Comparable<Entry> {
        int node;
        double maxProbability;

        Entry(int node, double maxProbability) {
            this.node = node;
            this.maxProbability = maxProbability;
        }

        @Override
        public int compareTo(Entry e) {
            return Double.compare(e.maxProbability, this.maxProbability);
        }
    }
}

 

📊 실행 결과

 

 

 

NOTE

• compareTo()는 int 값을 반환해야 하므로 아래 코드처럼 구현

@Override
public int compareTo(Entry e) {
    return Double.compare(e.maxProbability, this.maxProbability);
}