[LeetCode] 1514. Path with Maximum Probability

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

leetcode - Path with Maximum Probability

문제 유형 : 최단거리, 다익스트라, bfs, 우선순위 큐, 그래프

문제 난이도 : Medium

 

문제

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

 

n개의 노드와 무방향 가중치 그래프가 주어진다. edges[i] = [a, b]이면 a와 b사이에 거리가 있고, succProb[i]만큼의 건널 수 있는 확률이 주어진 것이다.

 

두 노드 start와 end가 주어진다. start부터 end까지 가는 가장 높은 확률을 구하시오.

길이 없으면 0을 반환하시오. 부동소수점 1e-5까지는 오차가 허용됩니다.

 

풀이

1. bfs를 이용한 다익스트라

큐에 {start, 1}를 넣고 시작한다. 현재 시작지점은 100% 보장되기에, 현재 위치의 확률은 1이다.

n개의 노드들별로 최대 확률을 저장하는 배열을 만든다.

bfs를 하면서, 인접한 노드들에 대해 배열의 해당 노드의 최대확률보다 높은 간선이 생기면 큐에 넣는다.

이를 큐가 빌 때까지 한다.

배열에는 최대 확률이 남아있다.

 

2. 우선순위 큐를 이용한 다익스트라

우선순위 큐에 {start, 1}을 넣고 시작한다. 이 우선순위 큐는 확률에 대해 최대 힙이어야 한다.

인접한 노드들부터 우선순위 큐에 노드와 새로운 확률을 반영하여 우선순위 큐에 넣는다.

만약 목표 노드에 도착하면, 현재 그 확률을 반환한다.

 

최대 힙으로 가장 높은 확률부터 탐색하기에, 먼저 탐색하는 경로가 현재 그 노드를 가는 것에 대해서 가장 높은 확률이다.

게다가 경로가 우회된다고 해서 확률이 더 높아지는 일은 없기에 괜찮다.

 

 

코드

C++ - bfs를 이용한 다익스트라

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        vector<vector<pair<int, double>>> graph(n);
        for(int i = 0; i < edges.size(); i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            graph[a].push_back({b, succProb[i]});
            graph[b].push_back({a, succProb[i]});
        }

        queue<pair<int, double>> q;
        q.push({start_node, 1.0});
        vector<double> prob(n, 0.0);
        prob[start_node] = 1.0;

        while(!q.empty()) {
            int currNode = q.front().first;
            double currProb = q.front().second;
            q.pop();

            for(const auto &next : graph[currNode]) {
                int nextNode = next.first;
                double nextProb = next.second * currProb;

                if(nextProb > prob[nextNode]) {
                    prob[nextNode] = nextProb;
                    q.push({nextNode, nextProb});
                }
            }
        }

        return prob[end_node];
    }
};

 

GO - 우선순위 큐를 이용한 다익스트라

type Edge struct {
	node int
	prob float64
}

type MaxHeap []Edge

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].prob > h[j].prob }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Edge))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func maxProbability(n int, edges [][]int, succProb []float64, start_node int, end_node int) float64 {
	graph := make([][]Edge, n)
	for i := 0; i < len(edges); i++ {
		a := edges[i][0]
		b := edges[i][1]
		prob := succProb[i]
		graph[a] = append(graph[a], Edge{node: b, prob: prob})
		graph[b] = append(graph[b], Edge{node: a, prob: prob})
	}

	prob := make([]float64, n)
	prob[start_node] = 1.0

	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)
	heap.Push(maxHeap, Edge{node: start_node, prob: 1.0})

	for maxHeap.Len() > 0 {
		curr := heap.Pop(maxHeap).(Edge)
		currNode := curr.node
		currProb := curr.prob

		if currNode == end_node {
			return currProb
		}

		for _, next := range graph[currNode] {
			nextNode := next.node
			nextProb := currProb * next.prob

			if nextProb > prob[nextNode] {
				prob[nextNode] = nextProb
				heap.Push(maxHeap, Edge{node: nextNode, prob: nextProb})
			}
		}
	}

	return 0.0
}