[프로그래머스] Lv.2 배달

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

프로그래머스

 

 

1. 해결방법

이 문제는 어렵지 않은, 그냥 전형적인 다익스트라 기본 문제이다.

양방향으로 이동이 가능하기 때문에 maps[]에 append할 때, 양방향으로 append해주는 것이 포인트이다.

그리고 1번에서 다른 마을까지의 거리 dist[] 리스트를 이용해서 해당 마을까지의 거리의 값을 구하고, dist에 값을 갱신한다.

거리가 K이하인 개수를 answer에 넣어주면 된다.

 

 

2. 정답코드

import heapq
import sys
def solution(N, road, K):
    INF = sys.maxsize
    
    answer = 0
    maps = [[] for _ in range(N + 1)]
    
    for r in road:
        a, b, c = r
        maps[a].append([c, b])
        maps[b].append([c, a])    
        
    dist = [INF] * (N + 1)
    heap = [[0, 1]]
    dist[1] = 0
    
    while heap:
        ew, ev = heapq.heappop(heap)
        if dist[ev] != ew: continue
        for nw, nv in maps[ev]:
            if dist[nv] > nw + ew:
                dist[nv] = nw + ew
                heapq.heappush(heap, [dist[nv], nv])
        
    return len([i for i in dist if i <=K])