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

Python으로 자동차 여행 시 최소 국가 간 이동 횟수와 총 비용 구하는 프로그램

여러 나라에 걸쳐 있는 도시들을 방문하는 자동차 여행을 계획한다고 가정해 보겠습니다. 도로 정보는 목록 'R'로 주어지며, 각 요소는 (x, y, cost) 형식입니다. 여기서 x는 해당 도로의 출발 도시, y는 도착 도시, cost는 그 도로를 이용할 때 드는 비용을 의미합니다. 또한 나라별 도시 정보를 담은 목록 'C'가 주어지는데, 각 요소는 하나의 나라를 나타내며 그 나라에 속한 도시들을 포함합니다.

출발 도시 's'에서 목적지 도시 'e'로 이동할 때, 국가 간 이동(국경 통과) 횟수를 최소화하는 경로를 찾아야 합니다. 동시에 여행의 총 비용도 계산하여 두 값을 함께 출력해야 합니다.

예를 들어 입력이 다음과 같다고 가정해 봅시다.
R = [[0, 1, 2], [1, 2, 2], [0, 2, 3], [1, 3, 3]], C = [[0], [1], [2, 3]], s = 0, e = 3
이 경우 출력은 (2, 5)가 됩니다.

도시 0에서 3으로 이동하려면 경로 0→1→3을 이용합니다. 이 경로에서 사용된 도로는 [0, 1, 2]와 [1, 3, 3]입니다. 따라서 국가 간 이동은 총 2회이고, 총 비용은 2 + 3 = 5입니다.

알고리즘 접근 방법

이 문제의 핵심 아이디어는 국경을 넘는 도로에 매우 큰 값(10^10)을 추가 비용으로 부과하는 것입니다. 이렇게 하면 하나의 거리 값 안에 두 가지 정보를 동시에 담을 수 있습니다. 최종 거리 값을 10^10으로 나눈 몫은 국가 간 이동 횟수가 되고, 나머지는 실제 이동 비용이 됩니다. 이후 일반적인 다익스트라(Dijkstra) 최단 경로 알고리즘을 적용하면 두 값을 한 번에 구할 수 있습니다.

구체적인 해결 단계는 다음과 같습니다.

  • 기본값이 0인 새로운 맵 cont를 생성합니다.
  • C의 각 인덱스 idx와 요소 item에 대해 다음을 수행합니다.
    • item의 각 k에 대해 cont[k] := idx로 설정합니다. (각 도시가 어느 나라에 속하는지 기록)
  • 리스트를 값으로 갖는 새로운 맵 adj_list를 생성합니다.
  • R의 각 (a, b, wt)에 대해 다음을 수행합니다.
    • 만약 cont[a] ≠ cont[b]라면, 즉 두 도시가 서로 다른 나라에 속한다면 wt := wt + 10^10으로 설정합니다.
    • adj_list[a]의 끝에 쌍 (b, wt)를 추가합니다.
  • 기본값이 10^20인 새로운 맵 distance를 생성하고 distance[s] := 0으로 설정합니다.
  • 새로운 집합 visited를 만듭니다.
  • 쌍 (0, s)를 포함하는 새로운 힙 t를 생성합니다.
  • t가 빌 때까지 다음을 반복합니다.
    • 힙에서 가장 작은 항목을 꺼내 (d, c)에 저장합니다.
    • c가 이미 visited에 있다면 다음 반복으로 넘어갑니다.
    • c를 visited에 추가합니다.
    • adj_list[c]의 각 (j, wt)에 대해, distance[j] > d + wt라면 distance[j] := d + wt로 갱신하고 힙 t에 쌍 (d + wt, j)를 삽입합니다.
  • (distance[e] // 10^10, distance[e] % 10^10) 쌍을 반환합니다.

예제 코드

더 잘 이해하기 위해 다음 파이썬 구현을 살펴보겠습니다.

from collections import defaultdict
from heapq import heappush, heappop

def solve(R, C, s, e):
    cont = defaultdict(int)
    for idx, item in enumerate(C):
        for k in item:
            cont[k] = idx

    adj_list = defaultdict(list)
    for a, b, wt in R:
        if cont[a] != cont[b]:
            wt += 10 ** 10
        adj_list[a].append((b, wt))

    distance = defaultdict(lambda: 10 ** 20)
    distance[s] = 0
    visited = set()

    t = [(0, s)]
    while t:
        d, c = heappop(t)
        if c in visited:
            continue
        visited.add(c)
        for j, wt in adj_list[c]:
            if distance[j] > d + wt:
                distance[j] = d + wt
                heappush(t, (d + wt, j))

    return distance[e] // 10 ** 10, distance[e] % 10 ** 10

print(solve([[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3))

입력

[[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3

출력

(2, 5)