[백준] 10217 KCM Travel

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

이전의 다익스트라 문제와는 조금 다르게 최소 거리 조건에 비용을 고려하여야 했습니다.

 

처음 문제를 풀이하였을 때, 1차원 배열을 이용하여 도시별 최소 소요 시간을 기록하였습니다.

그러면서 다음 목적지 탐색하는 과정에서 비용이 한도를 초과하는지 여부를 확인하였고, 한도를 넘지 않으면 무조건 최소 힙에 추가하여 탐색하는 과정으로 풀이하였습니다.

그러나 이 방법에는 최소 힙에 계속해서 요소가 추가되어 입력에 따라 메모리 초과가 발생하였습니다.

 

이후 2차원 배열을 이용하여 도시별 비용에 따른 최소 소요 시간을 기록하도록 하였습니다.

이를 통해 동일한 도시와 비용에 대한 중복적인 탐색이 발생하였을 때, 최소 소요 시간만을 기록할 수 있게 되었습니다.

그러나 이 방법 또한 '도시의 수 X 비용의 수' 만큼의 연산이 최소한으로 필요하였고, 최솟값이 갱신될 때마다 탐색이 계속 필요하여 최소 힙에 요소가 계속 추가되어 메모리 초과 문제가 발생하였습니다.

 

이를 해결하기 위해 A라는 도시를 3의 비용으로 2시간이 소요되었다면, 4 이후의 모든 비용은 2시간이 최소 소요 시간이 된다는 점을 이용하였습니다.

이렇게 도시와 비용에 따라 최소 시간을 기록을 하여 탐색하는 경우를 줄이게 되었고, 최소 힙에 추가되는 요소가 줄어들어 메모리 초과 문제를 해결할 수 있었습니다.

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')

def solution():
    h = [(0, 0, 0)]                                                 # 초깃값
    distance = [[1e10] * (M+1) for _ in range(N)]                   # 행 - 도시, 열 - 거리

    while h:
        d, c, v = heapq.heappop(h)                                  # 소요시간, 비용, 도착 도시

        for next in linked[v]:
            next_d = next[0] + d                                    # 다음 도시 가는데 소요 시간
            next_c = next[1] + c                                    # 다음 도시 가는데 발생 비용
            
            if next_c <= M and next_d < distance[next[2]][next_c]:  # 비용이 한도를 넘지 않고, 최소거리일때
                for j in range(next_c, M+1):                        # 다음 비용부터 한도비용까지
                    if next_d >= distance[next[2]][j]:
                        break
                    distance[next[2]][j] = next_d                   # 다음 소요 시간이 최소 소요시간이 됨
                heapq.heappush(h, (next_d, next_c, next[2]))        # 다음 탐색

    return distance[-1][-1]

T = int(sys.stdin.readline())

for _ in range(T):
    N, M, K = map(int, sys.stdin.readline().split())            # 공항 수, 지원 비용, 티켓 정보 수
    linked = [[] for _ in range(N)]                             # 도시별 항공편

    for _ in range(K):
        u, v, c, d = map(int, sys.stdin.readline().split())     # 출발, 도착, 비용, 소요시간
        linked[u-1].append((d, c, v-1))                         # 단방향
    
    answer = solution()

    if answer != 1e10:          # 출력
        print(answer)
    else:
        print('Poor KCM')

---

🔗 문제 링크

- https://www.acmicpc.net/problem/10217

10217번: KCM Travel

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다