파이썬 코딩테스트 강좌, 가장 빠른 버스 노선 구하기

본 강좌에서는 실제 취업 시험에서 자주 출제되는 알고리즘 문제 중 하나인 가장 빠른 버스 노선 구하기 문제를 다룹니다. 이 문제는 그래프 이론과 최단 경로 알고리즘을 활용하여 해결할 수 있습니다. 과정을 통해 알고리즘 문제 해결 능력을 강화하고, 파이썬 코드를 작성하는 데 필요한 다양한 기술을 익히도록 하겠습니다.

문제 설명

도시 N이 있으며, 1번에서 N번까지의 정점이 있습니다. 각 정점 사이에 여러 개의 버스 노선이 있으며, 버스 노선은 출발과 도착 정점, 소요 시간을 가지고 있습니다. 주어진 정보를 바탕으로, 1번 정점에서 N번 정점까지의 가장 빠른 경로와 그 소요 시간을 구하시오.

입력 형식

  • 첫 번째 줄에 정점의 개수 N (1 ≤ N ≤ 1000)과 버스 노선의 개수 M (1 ≤ M ≤ 10000) 이 주어집니다.
  • 그 다음 M 줄에 각 버스 노선의 정보가 u v w 형식으로 주어지며, u에서 v로 가는 버스의 소요 시간 w (1 ≤ w ≤ 10000)가 주어집니다.

출력 형식

  • 1번 정점에서 N번 정점까지 가는 가장 빠른 소요 시간을 출력합니다. 만약 경로가 없으면 -1을 출력합니다.

문제 해결 과정

1. 문제 이해

이 문제는 최단 경로를 찾는 문제로, 그래프 문제의 대표적인 유형입니다. 버스 노선을 그래프로 표현했을 때, 각 정점은 정류소에 해당하고, 간선은 버스 노선, 간선의 가중치는 소요 시간으로 생각할 수 있습니다. 우리가 해결하고자 하는 것은 1번 정점에서 N번 정점까지 가장 빠르게 이동하는 방법입니다.

2. 알고리즘 선택

최단 경로를 구하는 알고리즘은 여러 가지가 있지만, 여기서는 다익스트라 알고리즘을 사용할 것입니다. 다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 최단 경로를 찾는 데 효율적입니다. 주어진 버스 노선의 소요 시간이 모두 양수이므로 이 알고리즘이 적합합니다.

3. 알고리즘 구현

다익스트라 알고리즘의 기본 아이디어는 각 정점까지의 최단 경로 거리를 기록하는 배열을 유지하면서, 현재 가장 짧은 거리의 정점을 선택해가는 방식입니다. 구체적인 구현 과정은 다음과 같습니다.

# 필요한 라이브러리 import
import sys
import heapq

def dijkstra(N, edges):
    # 초기 거리 배열 설정
    distance = [float('inf')] * (N + 1)
    distance[1] = 0  # 시작점인 1번 정점의 거리는 0
    priority_queue = [(0, 1)]  # (거리, 정점)

    # 그래프 초기화
    graph = [[] for _ in range(N + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_distance > distance[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance_via_neighbor = current_distance + weight
            
            if distance_via_neighbor < distance[neighbor]:
                distance[neighbor] = distance_via_neighbor
                heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))

    return distance[N] if distance[N] != float('inf') else -1

# 입력 받기
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
result = dijkstra(N, edges)

print(result)

4. 예제 및 테스트 케이스

이 알고리즘의 적절함을 확인하기 위해, 여러 가지 입력 예제를 생각해보겠습니다.

예제 1

입력:
4 5
1 2 1
1 3 4
2 3 2
3 4 1
2 4 5

출력:
3

설명: 1번 정점에서 4번 정점까지의 최단 경로는 1 → 2 → 3 → 4로, 총 소요 시간은 3입니다.

예제 2

입력:
3 3
1 2 1
1 3 4
3 2 2

출력:
-1

설명: 1번 정점에서 2번 정점으로 도달할 수 있는 경로가 없으므로 -1을 출력합니다.

마무리

이번 강좌를 통해, 최단 경로를 구하는 다익스트라 알고리즘을 이용하여 가장 빠른 버스 노선 구하기 문제를 해결하는 방법을 배웠습니다. 알고리즘을 이해하고 구현하는 데 도움이 되셨기를 바랍니다. 앞으로의 코딩 테스트에서도 이러한 문제를 접할 수 있으므로 지속적으로 연습하시길 권장합니다.