BOJ 10217 KCM Travel python

2022년 11월 29일
#dijkstra#python#graph#dp#boj#algorithm

문제

KCM Travel

풀이

다익스트라, dp를 사용하여 풀이. [cost]*[v]로 dp를 설정했다. 다음 방문 노드까지의 비용이 m 이하이고, 비용이 dp에 저장된 값보다 작으면 dp를 갱신하고 큐에 넣어준다.

dp 구현 아이디어와 dp를 갱신 아이디어가 중요한 문제였다. 시간 제한이 아슬아슬해서 큐에서 뽑은 현재 거리와 dp에 저장된 거리를 비교해, 케이스를 줄이는 과정도 필요했다.

풀이 코드

import sys, heapq
rl = sys.stdin.readline
tn = int(rl())
for _ in range(tn):
    n, m, k = map(int, rl().split())
    g = [[] for _ in range(n)]
    for _ in range(k):
        u,v,c,d = map(int, rl().split())
        g[u-1].append((v-1,c,d))
 
    dp = [[sys.maxsize for _ in range(n)] for _ in range(m+1)]
    dp[0][0] = 0
    q = [(0,0,0)]
    while q:
        time, node, money = heapq.heappop(q)
        if dp[money][node] < time: continue
        
        for nnode, dm, dt in g[node]:
            if money+dm <= m:
                if dp[money+dm][nnode] > time+dt:
                    for i in range(money+dm, m+1):
                        if dp[i][nnode] > time+dt:
                            dp[i][nnode] = time+dt
                        else: break
                    heapq.heappush(q, (time+dt, nnode, money+dm))
    print(dp[m][-1] if dp[m][-1]!=sys.maxsize else "Poor KCM")

관련 글

백준 2927 남극탐험 Python
https://www.acmicpc.net/problem/2927 트리에서 노드 연결, 단일 업데이트, 구간합 쿼리를 수행하는 문제이다. 연결 여부는 union-find로 관리하고, 먼저 모든 연결 쿼리를 수행하여 HLD를 해준다. 이후, 순서대로 쿼리를 처리하면 된다. HLD 과...
BOJ 25910 게이트웨이 정하기 python
문제 게이트웨이 정하기 풀이 비트 연산의 특징을 알아야 풀 수 있는 문제였다. 1. 임의의 노드에서 시작한 결과를 dp에 저장한다. 2. 각 비트를 0인 그룹과, 1인 그룹으로 나눈다.(temp에 1일 경우만 저장) 3. 모든 노드에 대해 헤더와 XOR연산으로 비용을 구한다. 4....
programmers 행렬과 연산 python
문제 행렬과 연산 풀이 표를 적당히 쪼개서 deque로 풀면 된다. 맨 왼쪽 열과 맨 오른쪽 열을 따로 저장해서 deque 2개를 만들고, 각 행의 인덱스를 저장한 deque를 만든다. 연산 시, q, leftq, rightq에 저장된 마지막 인덱스를 맨 앞으로 옮겨준다. 연산 시...