백준 사이트의 10217 번 문제 KCM Travel 문제를 풀어보았습니다.
매주 월요일마다 진행하는 알고리즘 스터디에서 Python 언어를 활용해 풀이한 내용들을 공유합니다.
저는 알고리즘 문제를 풀어본 지 6개월이 넘은 것 같습니다. 그래서 그런지,, 머리가 백지상태가 되었어요. ㅠㅠ
먼저 저는 https://www.youtube.com/watch?v=B4Ivp_ebm4c 이 영상을 참고하여 문제를 풀었습니다.
목적 : 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길
조건 :
T : 테스트 케이스의 수
공항의 수 N (2 ≤ N ≤ 100) , 총 지원비용 M (0 ≤ M ≤ 10,000) , 티켓정보의 수 K (0 ≤ K ≤ 10,000)
K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착공항 v (1 ≤ u, v ≤ N, u ≠ v), 비용 c (1 ≤ c ≤ M, 정수),
그리고 소요시간 d (1 ≤ d ≤ 1,000)
인천은 언제나 1번 도시이고, LA는 언제나 N번 도시이다
찬민이 LA에 도착하는 데 걸리는 가장 짧은 소요시간을 출력한다
만약, LA에 도착할 수 없는 경우 "Poor KCM"을 출력한다.
문제를 처음 보고 다익스트라의 느낌이 확 와닿았습니다.
다만, 고려해야할 가중치가 1개 뿐인 전형적인 다익스트라의 알고리즘 문제들만 풀어봤기에,
위 문제는 고려해야할 조건이 (소요 시간,비용) 2가지인 문제라고 판단했고, 접근방법에서 부터 막혔습니다.
위 참고영상에서의 문제 풀이를 보고 다시 문제의 조건을 보니 냅색문제와 유사하다는 것을 알았습니다.
가방의 공간 : 물건의 무게 = 지원 비용 : 소요 시간 , 다소 차이가 있지만 이런 식으로 생각했습니다.
위와 같이 예를 들었을 때, ( 공항의 개수는 4개 입니다, 5,6 행은 무시해주세요 )
소요 비용을 순서대로 탐색하며 각각의 공항에서 이동가능한 경우를 찾아 최소 소요 시간을 적용합니다.
위의 예시는 도착 지점(N) 에서 지원 비용을 만족하지 못해 "Poor KCM" 이 결과로 출력됩니다.
이와 같은 문제들을 타개하기 좋은 방법은
고려할 조건을 분명히 하고, 1차원 또는 2차원의 테이블로 그려보는 것도 좋은 방법같습니다.
이하 다른 스터디원분들의 풀이 방법입니다.
import sys
import heapq
input = sys.stdin.readline
for _ in range(int(input())):
n, m, k = map(int,input().split())
graph = {i:[] for i in range(1, n+1)}
for i in range(k):
a, b, c, d = map(int,input().split())
graph[a].append([b, c, d])
visited = [[int(1e9)]*(n+1) for _ in range(m+1)]
q = [[0,0,1]]
while q:
cost, time, now = heapq.heappop(q)
if cost > visited[time][now]: continue
for v, c, d in graph[now]: continue
if time + c <= m and cost + d < visited[time+c][v]:
for i in range(time+c,m+1):
if visited[i][v] > cost + d: visited[i][v] = cost + d
else: break
heapq.heappush(q,(cost+d,time+c,v))
print(visited[m][n] if visited[m][n] != int(1e9) else "Poor KCM")import sys
INF = sys.maxsize
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N, M, K = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(K):
departure, arrival, expense, time = map(int,input().split())
graph[departure].append((arrival, expense, time))
arrival_expense = [[INF]*(M+1) for _ in range(N+1)]
arrival_expense[1][0] = 0
for e in range(M+1):
for d in range(1,N+1):
if arrival_expense[d][e] == INF:
continue
temp_time = arrival_expense[d][e]
for da, de, dt in graph[d]:
next_expense = de + e
if next_expense > M:
continue
arrival_expense[da][next_expense] = min(arrival_expense[da][next_expense],temp_time + dt)
result = min(arrival_expense[N])
print([result, 'Poor KCM'][result==INF])