프로그래머스 / 다익스트라 / 배달

문제

---

 

코딩테스트 연습 - 배달 | 프로그래머스 스쿨

프로그래머스

 

입출력

---

 

 

해설

---

 

1번 마을에서부터 N개의 마을까지 K 시간 이하로 걸리는 마을을 찾아내는 문제이다.

 

해당 문제를 다시 정의하자면 다음과 같을 것이다.

 

1번 정점으로부터 다른 정점까지 최단거리를 구하였을 때 cost가 K이하인 정점을 찾아내라.

 

이 말은 즉, 다익스트라를 돌렸을 때 마지막에 K이하인 정점들만 세주면 끝나는 문제이다.

 

평범한 다익스트라 문제이므로 별다른 풀이는 진행하지 않겠다.

 

정답코드

---

'''
'25. 12. 22.(월)
1. 1번 정점에서 각 정점으로 간다.
2. N개의 정점에서 K 시간 이하로 걸리는 마을에서만 주문을 받는다.

다익스트라를 이용하여 풀이 진행.
'''
from heapq import*
def solution(N: int, road: list, K: int):
    answer = 0
    
    pq = []
    
    graph = {i : []for i in range(1, N + 1)}
    for (a, b, c) in road:
        graph[a].append((b, c))
    
        graph[b].append((a, c))
    
    INF = 0x3f3f3f3f
    dp = [INF] * (N + 1)
    dp[1] = 0
    
    heappush(pq, (0, 1))
    while pq:
        dst, cur = heappop(pq)
        if dp[cur] < dst:continue
        
        for nxt, cost in graph[cur]:
            nxt_cost = dst + cost
            if dp[nxt] <= nxt_cost:continue
            dp[nxt] = nxt_cost
            heappush(pq, (nxt_cost, nxt))
              
    for i in range(1, N + 1):
        answer += dp[i] <= K
    return answer

 

깃허브 : https://buly.kr/5JOGlq5

유튜브 : https://youtu.be/KaFJWHc7XIU