백준 10217번 KCM Travel - python

📝python Algorithm

🔗 백준 10217 KCM Travel
https://www.acmicpc.net/problem/10217

🧲 코드

import sys
import math

def solution():
    n, total_cost, tickets = map(int, sys.stdin.readline().split())
    path = [[] for _ in range(n + 1)]
    for _ in range(tickets):
        start, end, cost, time = map(int, sys.stdin.readline().split())
        path[start].append((end, cost, time))
    MAX = math.inf
    temp = [[MAX] * (total_cost + 1) for _ in range(n + 1)]
    temp[1][0] = 0

    for cost in range(total_cost + 1):
        for node in range(n + 1):
            if temp[node][cost] != MAX:
                for next_node, next_cost, next_time in path[node]:
                    if next_cost + cost <= total_cost:
                        temp[next_node][next_cost + cost] = min(temp[next_node][next_cost + cost], temp[node][cost] + next_time)
    
    result = min(temp[n])
    if result == MAX:
        print('Poor KCM')
    else:
        print(result)
        
T = int(input())
for _ in range(T):
    solution()

🧲 문제 생각

🔍 어려웠다... 당연히 Dijkstra Algorithm 으로 손쉽게 풀릴줄 알았는데, Dijkstra Algorithm 에 적용하면서 깨달았다.
time, cost 두 가지 조건이 주어져 꼬이는 부분이 분명히 있다는 걸
🔍아직 2차원 배열을 바로바로 생각하면서 문제 풀이를 하는게 익숙하지 않은데 몇시간 잡고있다보니 확실히 느는 것 같다.
🔍 https://roamingman.tistory.com/46 -> 참고 블로그 및 영상

💡 떠올려아할 생각

🔍 다익스트라를 사용하려면 그리디한 선택을 매 번 진행해야 하는데 cost 값이 최소가 되어야 하고, time도 최소가 되어야 하므로 어느 하나를 잡고 다익스트라를 사용할 수 없다.
📚 따라서 전체 탐색을 해야 하며 주어진 총 비용과 노드들로 2차원 배열을 만들어야 한다.
🔍총 비용으로 2차원 배열을 만든다는 것 자체가 시간이 오래걸릴 것 같아 생각에 존재조차 안했다.

💡 참고로 위 코드는 python3로는 시간초과가 난다. pypy3로 진행했다.

🧲 짧은 해설

🔍위에서 말한대로

temp = [[MAX] * (total_cost + 1) for _ in range(n + 1)]

총 비용과 노드 수로 2차원 배열을 만들어

for cost in range(total_cost + 1):
        for node in range(n + 1):
            if temp[node][cost] != MAX:
                for next_node, next_cost, next_time in path[node]:
                    if next_cost + cost <= total_cost:
                        temp[next_node][next_cost + cost] = min(temp[next_node][next_cost + cost], temp[node][cost] + next_time)

티켓 정보에 있는 다음를 찾아가며 최소 시간으로 초기화 주며 for 문을 돌렸다.