[Python/프로그래머스]배달_다익스트라

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

 

 

🐾 20221014

 

 

 

전형적인 다익스트라 문제 + 리스트 돌면서 k보다 작은 수 구해 return 하면 된다. 

 

 

이 문제는 양방향이다!!

 

양방향인지 단방향인지 잘 보고 해야한다.

 

 

 

 

 

 

코드 : 

import heapq

def dijkstra(distance,mp) :
    q = []
    # dist는 0, node 시작 번호는 1 
    heapq.heappush(q,[0,1])
    distance[1] = 0
    
    while q :
        dist, node = heapq.heappop(q)
        # 이미 저장되어 있는 값보다  크면 볼필요 없음 
        if distance[node] < dist : continue 
   		# 지금 노드에서 갈 수 있는 노드를 모두 탐색 
        for i in mp[node] :
            cost = dist + i[1]
            # 지금 노드를 거쳐서 가는 값이 원래 값보다 작으면 
            if distance[i[0]] > cost :
            	# 갱신 
                distance[i[0]] = cost
                heapq.heappush(q,[cost,i[0]])

def solution(N, road, K):
    answer = 0
    distance = [int(1e9)] * (N+1)
    mp = [[] for _ in range(N+1)]
    for u,v,w in road :
        mp[u].append([v,w])
        mp[v].append([u,w])
    
    dijkstra(distance,mp)
    
    for i in range(1,N+1) :
        if distance[i] <= K : answer+=1 

    return answer

 

 

참고할 내 포스팅 : 

https://what-am-i.tistory.com/400

[Python]다익스트라_최단경로알고리즘 (feat. heap)