문제 개요
노드가 n개인 무방향 가중치 그래프가 주어진다고 가정해 봅시다(노드는 0부터 번호가 매겨집니다). 그래프는 간선 리스트 형태로 입력되며, 각 간선 e마다 해당 간선을 통과할 때의 성공 확률인 probability[e]가 함께 제공됩니다. 또한 시작 노드와 끝 노드도 주어지는데, 우리의 목표는 시작 노드에서 끝 노드까지 이동하는 경로 중 성공 확률이 가장 높은 경로를 찾아 그 확률값을 반환하는 것입니다. 만약 어떤 경로도 존재하지 않는다면 0을 반환하면 됩니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
이 경우 출력은 0.25가 됩니다. 노드 0에서 노드 2로 가는 경로는 두 가지입니다. 하나는 두 노드를 직접 잇는 간선을 이용하는 방법으로 확률이 0.2이고, 다른 하나는 노드 1을 거쳐 가는 방법으로 확률이 0.5 × 0.5 = 0.25입니다. 따라서 더 큰 값인 0.25가 정답이 됩니다.
풀이 접근 방법
이 문제는 너비 우선 탐색(BFS)을 응용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 일반적인 최단 거리 탐색 대신, 각 노드에 도달할 수 있는 확률의 최댓값을 기준으로 탐색을 진행하는 것입니다. 단계별로 살펴보겠습니다.
- g := 주어진 간선 리스트로 그래프를 만들고, 확률 값을 가중치로 사용합니다.
- q := 큐(queue) 자료구조를 준비합니다.
- (start, 1)을 q에 삽입합니다.
- visited := 각 노드에 도달한 최대 확률을 기록하는 맵(map)입니다.
- q가 빌 때까지 다음 과정을 반복합니다.
- (node, prob) := q에서 첫 번째 항목을 꺼냅니다.
- 만약 visited[node] > prob라면, 이미 더 높은 확률로 해당 노드를 방문한 적이 있으므로 다음 반복으로 넘어갑니다.
- 그렇지 않다면 visited[node] := prob로 갱신합니다.
- g[node]에 있는 모든 인접 노드 adj와 그 확률 nextProb에 대해, visited[adj] < prob × nextProb이라면 (adj, prob × nextProb)을 q의 끝에 삽입합니다.
- 모든 탐색이 끝나면 visited[end]를 반환합니다.
이 알고리즘에서 주목할 점은, 새로 계산된 누적 확률이 기존에 기록된 값보다 클 때만 큐에 추가한다는 것입니다. 덕분에 확률이 낮아지는 비효율적인 경로 탐색을 사전에 차단하여 불필요한 연산을 크게 줄일 수 있습니다.
아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.
예시 코드
from collections import defaultdict, deque
def solve(edges, probability, start, end):
g = defaultdict(list)
for i in range(len(edges)):
src, dst = edges[i][0], edges[i][1]
prob = probability[i]
g[src].append((dst, prob))
g[dst].append((src, prob))
q = deque()
q.append((start, 1))
visited = defaultdict(int)
while q:
node, prob = q.popleft()
if visited[node] > prob:
continue
else:
visited[node] = prob
for adj, nextProb in g[node]:
if visited[adj] < prob * nextProb:
q.append((adj, prob * nextProb))
return visited[end]
edges = [[0,1],[1,2],[0,2]]
probability = [0.5,0.5,0.2]
start = 0
end = 2
print(solve(edges, probability, start, end))
입력
[[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2
출력
0.25