프로그래머스 - (python) 배달

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

코딩테스트 연습 - 배달

 

1. 유형

그래프

 

2. 알고리즘

다익스트라

 

3. 풀이

기본적인 다익스트라 구현이다.

 

1) 인접리스트 만들기

2) 다익스트라 포멧에 맞게 작성

 

코드.

import heapq
import sys
def solution(N, roads, K):
    answer = 0
    pq = []
    list = [[] for _ in range(N+1) ]
    visited = [False]*(N+1)
    sum = [sys.maxsize]*(N+1)
    sum[1] = 0
    heapq.heappush(pq, [0,1])#가중치, 노드
    for road in roads:
        list[road[0]].append([road[1], road[2]])
        list[road[1]].append([road[0], road[2]])
    for _ in range(N):
        node, dist= 0,0
        while pq:
            dist, node = heapq.heappop(pq)
            if not visited[node]:
                visited[node] = True
                break
        for nextNode, nextDist in list[node]:
            if nextDist+sum[node] <= sum[nextNode]:
                sum[nextNode] = nextDist+sum[node]
                heapq.heappush(pq, [nextDist+sum[node], nextNode])
    for i in sum:
        answer = answer+1 if i<=K else answer
    return answer