[ 프로그래머스 / PYTHON ] 배달

문제설명 - 다익스트라 문제

배달
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

내코드

[ALG] 다익스트라 알고리즘 정리

heap 사용 그냥 큐를 사용하는 것 보다 훨씬 빠름
==> 힙 써주면 최단 거리 노드만 보기에 훨씬 효율적이지만, 써주지 않으면 모든 연결된 노드를 보기 때문에 비효율적임
==>이 때문에 heapq를 사용했을 때 정점의 개수는 많지만, 간선의 개수는 적을 때 훨씬 효율적이라는 것.
! heap정렬을 사용하기 위해 heapq에 넣을 때 비용을 앞에둬야 앞의 내용을 기준으로 자동정렬해줌.

import heapq
def dijc(li,sd,K):
    q = []
    heapq.heappush(q,(0,1))
    sd[1] = 0
    while q:
        d,n = heapq.heappop(q)
        if d > K: continue
        for vil in li[n]:
            if vil[1] + d < sd[vil[0]]:
                sd[vil[0]] = vil[1] + d
                heapq.heappush(q,(vil[1] + d,vil[0]))
    return sd

def solution(N, road, K):
    inf = 1000000000
    answer = 0
    sd = [inf for i in range(N+1)]
    li = [[] for i in range(N+1)]

    for rd in road:
        li[rd[0]].append((rd[1],rd[2]))
        li[rd[1]].append((rd[0],rd[2]))
    sd = dijc(li,sd,K)
    
    for i in range(N+1):
        if sd[i] <= K:  answer += 1
    return answer

deque 사용

from collections import deque
def dijc(li,sd,K):
    q = deque([(1,0)])
    sd[1] = 0
    while q:
        n,d = q.popleft()
        if d > K: continue
        for vil in li[n]:
            if vil[1] + d < sd[vil[0]]:
                sd[vil[0]] = vil[1] + d
                q.append([vil[0],vil[1] + d])
    return sd

def solution(N, road, K):
    inf = 1000000000
    answer = 0
    sd = [inf for i in range(N+1)]
    li = [[] for i in range(N+1)]

    road.sort(key = lambda x:x[2])
    for rd in road:
        li[rd[0]].append((rd[1],rd[2]))
        li[rd[1]].append((rd[0],rd[2]))
    sd = dijc(li,sd,K)
    
    for i in range(N+1):
        if sd[i] <= K:  answer += 1
    return answer