Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 최소값 정점에서 최대값 정점까지의 최소 비용 경로 찾기

무방향 가중치 그래프가 주어졌을 때, 값이 가장 작은 정점에서 값이 가장 큰 정점까지 이동 비용이 최소가 되는 경로를 찾아야 한다고 가정해 보겠습니다.

여기서 이동 비용은 다음과 같이 계산됩니다. 정점 A에서 C로 가는 경로가 A → B → C라고 할 때, A에서 B로 이동하는 비용이 10이고 B에서 C로 이동하는 비용이 20이라면, A에서 C까지의 총 비용은 다음과 같습니다.

(A에서 B까지의 이동 비용) + (B에서 C까지의 이동 비용 − 노드 B까지의 누적 비용)

즉, 10 + (20 − 10) = 20이 됩니다. 새 간선의 가중치가 현재 누적 비용보다 클 때만 차액이 추가되고, 그렇지 않으면 비용이 그대로 유지되므로, 결국 경로의 총 비용은 해당 경로에 포함된 간선 가중치 중 최댓값과 같습니다. 따라서 우리가 구해야 하는 것은 주어진 그래프에서 첫 번째 노드(최소값 노드)에서 마지막 노드(최대값 노드)까지 가능한 한 최소의 이동 비용을 만드는 경로입니다.

예제

예를 들어 입력이 다음과 같다고 해보겠습니다.

파이썬으로 최소값 정점에서 최대값 정점까지의 최소 비용 경로 찾기

이 경우 출력은 15입니다.

정점 1과 정점 4 사이에는 두 개의 경로가 존재합니다. 최적 경로는 1 → 2 → 4이며, 이 경로의 비용은 10 + (15 − 10) = 15입니다. 반면 나머지 경로(1 → 4 직행)의 비용은 20이 됩니다.

해결 접근 방식

이 문제를 해결하기 위해 다음 단계를 따릅니다.

  • adjList := 빈 리스트를 값으로 갖는 새로운 맵(인접 리스트)을 생성합니다.
  • edges의 각 항목에 대해 다음을 수행합니다.
    • u := item[0]
    • v := item[1]
    • w := item[2]
    • adjList[u]의 끝에 쌍 (w, v)를 삽입합니다.
    • adjList[v]의 끝에 쌍 (w, u)를 삽입합니다.
  • q := 새로운 최소 힙(min-heap)을 생성합니다.
  • v_list := 방문한 노드를 추적하기 위한 새로운 집합(set)을 생성합니다.
  • q의 끝에 (0, 1)을 삽입합니다.
  • flag := True로 설정합니다.
  • q가 비어 있지 않은 동안 다음을 반복합니다.
    • c := q에서 가장 작은 항목을 꺼냅니다(pop).
    • c[1]이 v_list에 이미 존재하면 다음 반복으로 넘어갑니다.
    • v_list에 c[1]을 추가합니다.
    • c[1]이 n과 같다면
      • flag := False로 설정하고 c[0]을 반환합니다.
    • adjList[c[1]]의 각 u에 대해 다음을 수행합니다.
      • u[1]이 v_list에 없다면
        • out := (max(u[0], c[0]), u[1]) — 즉, 지금까지의 누적 비용과 새 간선 가중치 중 더 큰 값을 우선순위로 사용합니다.
        • out을 힙 q에 push합니다.
  • 반복이 끝난 후에도 flag가 True라면 목적지에 도달할 수 없으므로 -1을 반환합니다.

핵심 아이디어는 일반적인 다익스트라(Dijkstra) 알고리즘에서 거리를 합산하는 대신, 경로상 간선 가중치의 최댓값을 기준으로 우선순위 큐를 운영한다는 점입니다. 이렇게 하면 항상 '현재까지의 최대 간선 비용'이 가장 작은 경로부터 탐색하게 되어, 목적지에 처음 도달했을 때의 값이 곧 최소 비용이 됩니다.

구현 예시

아래 구현을 통해 더 잘 이해해 보겠습니다.

from collections import defaultdict
import heapq
def solve(n, edges):
    adjList = defaultdict(list)
    for item in edges:
        u, v, w = map(int, item)
        adjList[u].append((w,v))
        adjList[v].append((w,u))
    q = []
    v_list = set()
    q.append((0,1))
    flag = True
    while q:
        c = heapq.heappop(q)
        if c[1] in v_list:
            continue
        v_list.add(c[1])
        if c[1] == n:
            flag = False
            return c[0]
        for u in adjList[c[1]]:
            if u[1] not in v_list:
                out = (max(u[0],c[0]),u[1])
                heapq.heappush(q,out)
    if flag:
        return -1

print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]))

입력

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]

출력

15