파이썬으로 최종 목적지까지 도달하는 데 드는 최소 버스 비용 구하기

문제 개요

n × 3 크기의 행렬이 주어집니다. 각 행은 [src, dest, id] 세 개의 필드로 구성되며, 이는 해당 버스가 src(출발지)에서 dest(도착지)까지 운행한다는 의미입니다. 새로운 버스에 탑승할 때마다 1단위의 비용이 들지만, 같은 버스에 계속 타고 있는 동안에는 추가 비용이 발생하지 않습니다. 위치 0에서 출발해 가장 먼 최종 정류장(주어진 위치 중 가장 큰 값)까지 이동하는 데 필요한 최소 비용을 구하고, 경로가 존재하지 않으면 -1을 반환해야 합니다.

입력 예시

이 경우 출력은 2입니다. 위치 0에서 0번 버스를 타고 위치 3까지 이동한 뒤, 1번 버스로 갈아타 위치 5(최종 목적지)에 도달할 수 있기 때문입니다.

해결 전략

이 문제는 각 정류장과 버스 조합을 그래프의 상태로 보고, 다익스트라(Dijkstra) 알고리즘처럼 우선순위 큐(최소 힙)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 현재 위치에 어떤 버스로 도착했는지 함께 추적하는 것입니다. 같은 버스로 이동하면 비용이 늘지 않고, 다른 버스로 환승할 때만 비용이 1 증가합니다.

단계별 절차는 다음과 같습니다.

1. start를 0으로 초기화합니다.
2. target은 주어진 행렬에서 가장 큰 위치 값으로 설정합니다.
3. 인접 리스트 adj를 만들고, 각 연결 정보(src, dest, id)에 대해 adj[src] 끝에 (dest, id)를 추가합니다.
4. 우선순위 큐 hp를 (0, start, -1)로 초기화합니다. 여기서 -1은 아직 탑승 중인 버스가 없음을 의미합니다.
5. 방문 기록용 맵 seen을 준비합니다.
6. hp가 빌 때까지 다음을 반복합니다.
   • 힙에서 최상위 요소 (cost, cur_pos, cur_bus)를 꺼냅니다.
   • cur_pos가 target과 같으면 cost를 반환합니다.
   • cur_bus가 이미 seen[cur_pos]에 있다면 다음 반복으로 건너뜁니다.
   • 그렇지 않으면 cur_bus를 seen[cur_pos]에 추가합니다.
   • adj[cur_pos]의 모든 (nex_pos, nex_bus)에 대해 다음을 수행합니다.
     • next_cost를 cost로 초기화합니다.
     • nex_bus가 cur_bus와 다르면 next_cost를 1 증가시킵니다.
     • (next_cost, nex_pos, nex_bus)를 힙에 삽입합니다.
7. 루프가 종료되면 -1을 반환합니다.

구현 코드

from collections import defaultdict
from heapq import heapify, heappop, heappush


class Solution:
   def solve(self, connections):
      start = 0
      target = max(max(y, x) for y, x, _ in connections)

      adj = defaultdict(list)
      for f, t, id in connections:
         adj[f].append((t, id))

      hp = [(0, start, -1)]
      seen = defaultdict(set)

      while hp:
         cost, cur_pos, cur_bus = heappop(hp)
         if cur_pos == target:
            return cost
         if cur_bus in seen[cur_pos]:
            continue
         seen[cur_pos].add(cur_bus)

         for nex_pos, nex_bus in adj[cur_pos]:
            next_cost = cost
            if nex_bus != cur_bus:
               next_cost += 1
            heappush(hp, (next_cost, nex_pos, nex_bus))

      return -1


ob = Solution()
matrix = [
   [0, 1, 0],
   [1, 2, 0],
   [2, 3, 0],
   [3, 5, 1],
   [5, 0, 2]
]
print(ob.solve(matrix))

입력

matrix = [[0, 1, 0],
[1, 2, 0],
[2, 3, 0],
[3, 5, 1],
[5, 0, 2]]

출력

2

복잡도 분석

시간 복잡도는 O(E log E)입니다. 여기서 E는 총 연결(간선) 수로, 각 간선이 힙에 최대 한 번씩 삽입되고 힙 연산에 로그 시간이 소요되기 때문입니다. 공간 복잡도는 인접 리스트, 방문 기록, 힙 저장을 위해 O(E)입니다.