[코테연습] 1514. Path with Maximum Probability

- 다익스트라 알고리즘 문제

 

https://leetcode.com/problems/path-with-maximum-probability/description/?envType=daily-question&envId=2024-08-27

 

- 문제분석

1. 노드의 간선의 갯수, 노드의 cost 등이 주어지고 다익스트라 or 플로이드와셜 알고리즘을 이용하여 최단거리를 구하는 문제.

2. 특이한점은 cost 가 실수 ( double ) 로 되어있어서 해당 문제를 해결해야한다.

 

- 문제풀이

1. int[][] edges 2중 배열을 List<List<Node>> graph 배열로 초기화한다.

1-1. Node 는 int index 와 double cost 로 class 를 만들어 초기화한다.

2. graph 배열에는 각 노드의 간선과 cost 값을 넣어준다.

3. 다익스트라 알고리즘을 이용하여 함수를 만든다.

3-1. nextValue = 현재value * 다음 node cost 값 으로 초기화하여 문제에 대응한다.

 

class Solution {
    /**
    
    1. start end node 가 연결되어있는지 여부 확인
    2. start end 가 가장 가까운 노드를 구한다.
    --> 다익스트라
     */
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        List<List<Node>> graph = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

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


        return dijktra(n, start_node, end_node, graph);
    }

    double dijktra(int n, int start, int end, List<List<Node>> graph) {
        boolean[] visited = new boolean[n];
        double[] dist = new double[n];

        PriorityQueue<double[]> pq = new PriorityQueue<>((o1, o2)-> Double.compare(o2[0], o1[0]));
        pq.offer(new double[]{1, start});
        dist[start] = 1;

        while(!pq.isEmpty()) {
            double[] current = pq.poll();
            double value = current[0];
            int idx = (int) current[1];
            
            if ( idx == end) {
                return value;
            }

            for (Node _node : graph.get(idx)) {
                double nextValue = value * _node.cost;
                if (nextValue > dist[_node.index]) {
                    dist[_node.index] = nextValue;
                    pq.offer(new double[]{nextValue, _node.index});
                }
            }
        }
       
        return 0;
    }

    class Node implements Comparable<Node>{
        int index;
        double cost;
        
        public Node(int index, double cost) {
            this.index = index;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node o) {
            return Double.compare(this.cost, o.cost);
        }

        public String toString() {
            return "[ "+this.index+", "+this.cost+" ]";
        }
    }
}