[알고리즘] 프로그래머스 - 배달
내 풀이
from collections import defaultdict
import sys
import heapq
def dijkstra(start, graph, N, K):
distances = [sys.maxsize] * (N + 1)
distances[start] = 0
heap = []
heapq.heappush(heap, (0, start))
while heap:
cost, node = heapq.heappop(heap)
for adj_node in graph[node]:
if distances[adj_node[1]] > cost + adj_node[0]:
distances[adj_node[1]] = cost + adj_node[0]
heapq.heappush(heap, (cost + adj_node[0], adj_node[1]))
count = 0
for i in distances:
if i <= K:
count += 1
return count
def solution(N, road, K):
graph = defaultdict(list)
for edge in road:
graph[edge[0]].append((edge[2], edge[1])) # (cost, node)
graph[edge[1]].append((edge[2], edge[0]))
return dijkstra(1, graph, N, K)
다익스트라를 heap을 이용해서 더 효율적으로 구현해봤다.
Author And Source
이 문제에 관하여([알고리즘] 프로그래머스 - 배달), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@injoon2019/알고리즘-프로그래머스-배달저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)