[LeatCode] Medium 1514 Path with Maximum Probability (Java)

문제 링크

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

문제 풀이

설명

주어진 그래프에서 시작 노드부터 끝 노드에 도착할 수 있는 경로 중 최대 확률을 구하는 문제입니다.

예제1

입력

n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2

출력

0.25

예제2

입력

n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2

출력

0.3

예제3

입력

n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2

출력

0

접근 방식

이 문제는 그래프 탐색 문제로, 주어진 간선들의 확률을 바탕으로 시작 노드부터 끝 노드에 도착할 수 있는 경로 중 최대 확률을 구하는 문제입니다. 이 문제를 풀기 위해서는 다익스트라 알고리즘을 변형한 방법을 사용할 수 있습니다. 다익스트라 알고리즘은 최단 경로를 찾는 알고리즘이지만, 이를 최대 확률 경로로 변형하여 사용할 수 있습니다.

확률을 구할 때 곱셈을 사용하므로, 최대 확률을 구하는 데 있어서 우선순위 큐를 활용하여 가장 큰 확률부터 탐색해야 합니다.

알고리즘

• 주어진 간선들을 통해 인접 리스트를 구성
• 확률이 가장 큰 노드부터 처리할 수 있도록 우선순위 큐를 사용
• 다익스트라 알고리즘 변형:
  • dist[] 배열을 사용하여 각 노드에 대해 도달 가능한 최대 확률 계산
    • dist[start]는 시작 노드의 확률을 1로 설정하고, 나머지 노드는 처음에 0으로 설정
    • 경로를 따라갈 때마다 그 경로에서 얻을 수 있는 최대 확률을 갱신
  • 큐에서 꺼낸 노드를 기반으로 연결된 노드들의 확률을 갱신
    • nextWeight = cur.weight * next.weight로 새로운 경로의 확률 계산
    • 만약 현재까지 기록된 next 노드의 확률보다 nextWeight가 더 크다면, dist[next]를 nextWeight로 갱신하고, 그 노드를 큐에 추가
  • 큐에서 가장 큰 확률을 가진 노드를 먼저 처리
    • 우선순위 큐를 사용하여, 가장 큰 확률을 가진 노드부터 처리

구현

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class Node {
    int v;
    double weight;

    public Node(int v, double weight) {
        this.v = v;
        this.weight = weight;
    }
}

class Solution {
    public static List<List<Node>> graph;

    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

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

        return dijkstra(n, start_node, end_node);
    }

    private double dijkstra(int n, int start_node, int end_node) {
        double[] dist = new double[n];
        dist[start_node] = 1;

        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Double.compare(o2.weight, o1.weight));
        pq.add(new Node(start_node, 1));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (cur.weight < dist[cur.v]) continue;

            for (Node next : graph.get(cur.v)) {
                double nextWeight = cur.weight * next.weight;
                if (dist[next.v] < nextWeight) {
                    dist[next.v] = nextWeight;
                    pq.add(new Node(next.v, nextWeight));
                }
            }
        }

        return dist[end_node];
    }
}

시간 복잡도

• 그래프 구성: O(E) (E는 간선 수)
• 다익스트라 탐색: O((V + E) log V) (V는 노드 수, E는 간선 수)
  • 우선순위 큐에서 각 노드에 대해 log V의 시간 소요
• 전체 시간 복잡도: O((V + E) log V)