백준 KCM Travel [10217] 파이썬(Python) 코드 + 해설

백준 KCM Travel 10217번 문제

문제 설명

찬민이는 인천에서 LA로 여행을 가려고 합니다. 하지만 구글에서 여행 비용을 최대 M원까지 지원해주기 때문에, 이 예산 내에서 가장 빠르게 LA에 도착해야 합니다. 각 도시 간의 항공편은 비용과 시간이 주어집니다.

목표: 인천(1번 도시)에서 LA(N번 도시)까지 비용 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 시간을 구하는 것입니다. 만약 예산 내에서 도착할 수 없다면 "Poor KCM"을 출력합니다.

---

입력 조건

• T: 테스트 케이스의 수 (1 ≤ T ≤ 100)
• 각 테스트 케이스:
  • N: 공항의 수 (2 ≤ N ≤ 100)
  • M: 지원 비용 (0 ≤ M ≤ 10,000)
  • K: 티켓 정보의 수 (0 ≤ K ≤ 10,000)
  • K개의 티켓 정보:
    • u, v: 출발 공항과 도착 공항 (1 ≤ u, v ≤ N)
    • c: 비용 (1 ≤ c ≤ M)
    • d: 소요 시간 (1 ≤ d ≤ 1,000)

---

출력 조건

• 각 테스트 케이스마다 한 줄에 인천에서 LA까지 도착하는 데 걸리는 가장 짧은 소요 시간을 출력합니다.
• 만약 도착할 수 없다면 "Poor KCM"을 출력합니다.

---

문제 접근

이 문제는 최소 비용 내에서 최소 시간을 찾는 최단 경로 문제입니다. 일반적인 최단 경로 알고리즘인 다익스트라 알고리즘은 하나의 가중치만을 고려하지만, 이 문제에서는 비용과 시간 두 가지 가중치를 동시에 고려해야 합니다.

따라서 다음과 같은 방법으로 문제를 해결할 수 있습니다:

1. 다이나믹 프로그래밍(DP)과 다익스트라 알고리즘의 결합:
   • 비용과 시간을 함께 고려하기 위해 DP 배열을 사용합니다.
   • 우선순위 큐를 사용하여 탐색을 최적화합니다.
2. DP 배열의 정의:
   • dp[node][cost]는 노드 node에 비용 cost를 사용하여 도달했을 때의 최소 시간을 의미합니다.
3. 우선순위 큐를 사용한 탐색:
   • (시간, 비용, 노드)를 원소로 하는 우선순위 큐를 사용하여 최소 시간부터 탐색합니다.
   • 이미 더 작은 시간에 해당 노드에 도달한 경우는 스킵하여 불필요한 탐색을 줄입니다.

---

알고리즘 구현

1. 데이터 구조 및 초기화

• 그래프 저장:
  • 인접 리스트를 사용하여 그래프를 저장합니다.
  • 각 간선은 (도착 노드, 비용, 시간)의 정보를 가집니다.
• DP 배열 초기화:
  • dp = [[INF] * (M + 1) for _ in range(N + 1)]
  • 모든 값을 무한대로 초기화하고, 시작점 dp[1][0] = 0으로 설정합니다.
• 우선순위 큐 초기화:
  • heap = []
  • 시작점 (0, 0, 1)을 큐에 추가합니다.

2. 다익스트라 알고리즘 적용

• 큐에서 원소를 꺼내어 탐색:
  • 현재 시간, 비용, 노드를 꺼냅니다.
  • 현재 시간이 dp[node][cost]보다 큰 경우 스킵합니다.
  • 현재 노드에서 이동 가능한 모든 간선을 탐색합니다.
• 다음 노드로의 이동:
  • 다음 비용 next_cost = cost + c_edge
  • 다음 시간이 next_time = time + d_edge
  • 예산을 초과하는 경우 스킵합니다.
  • dp[next_node][next_cost] > next_time인 경우 갱신하고 큐에 추가합니다.

3. 결과 출력

• dp[N]에서 최소 시간을 찾아 출력합니다.
• 만약 도달할 수 없다면 "Poor KCM"을 출력합니다.

---

백준 10217 KCM Travel 파이썬(Python) 정답 코드

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

T = int(input())

for _ in range(T):
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(K):
        u, v, c, d = map(int, input().split())
        graph[u].append((v, c, d))

    dp = [[INF] * (M+1) for _ in range(N+1)]
    dp[1][0] = 0  # 시작점 설정

    heap = []
    heapq.heappush(heap, (0, 0, 1))  # (시간, 비용, 노드)

    while heap:
        time, cost, node = heapq.heappop(heap)
        if dp[node][cost] < time:
            continue
        for v, c_edge, d_edge in graph[node]:
            next_cost = cost + c_edge
            next_time = time + d_edge
            if next_cost > M:
                continue
            if dp[v][next_cost] > next_time:
                dp[v][next_cost] = next_time
                heapq.heappush(heap, (next_time, next_cost, v))

    result = min(dp[N])
    if result == INF:
        print("Poor KCM")
    else:
        print(result)

 

---

백준 10217 KCM Travel 코드 설명

 

1. 입력 처리

• T를 입력받고, 각 테스트 케이스마다 N, M, K를 입력받습니다.
• 각 티켓 정보를 graph에 저장합니다.

2. DP 배열 및 우선순위 큐 초기화

• dp 배열을 무한대로 초기화하고, 시작점 dp[1][0] = 0으로 설정합니다.
• 우선순위 큐 heap을 생성하고 시작점 (0, 0, 1)을 추가합니다.

3. 다익스트라 알고리즘 적용

• 큐에서 (시간, 비용, 노드)를 꺼냅니다.
• 이미 더 작은 시간에 해당 노드에 도달한 경우 스킵합니다.
• 현재 노드에서 이동 가능한 모든 간선을 탐색합니다.
• 다음 노드로 이동할 때의 비용과 시간이 예산과 현재 dp 값보다 작으면 갱신하고 큐에 추가합니다.

4. 결과 출력

• dp[N]에서 최소 시간을 찾아 출력합니다.
• 도달할 수 없는 경우 "Poor KCM"을 출력합니다.

백준 10217 KCM Travel 정답 코드

 

도움이 되셨다면 공감과 댓글 부탁드립니다.