프로그래머스 - Lv.2 배달 (다익스트라) Python

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

해당 문제는 마을의 갯수, [시작점, 도착점, 거리]를 요소로 하는 배열, 음식점에서 배달 가능한 거리라고 했을 때, 음식점이 있는 마을인 1번 마을에서, 몇 개의 마을에 배달이 가능한지 묻는 문제다.

문제 풀이 방식

특정 노드에서, 각 노드까지의 최소 가중치를 구해야 하므로, 다익스트라 알고리즘으로 접근했다. 다만, 다익스트라 알고리즘 구현 과정에서, 거리가 K를 초과하는 경우는 결괏값에 포함되지 않기 때문에 해당 경우는 연산하지 않는 방식으로 불필요한 연산을 최소화하려 했다.

다익스트라 관련 포스팅

2023.11.14 - [개발/algorithm] - 백준1916 - 최소 비용 구하기 (다익스트라) Python

 

전체 소스 코드

from heapq import heappush, heappop

def solution(N, road, K):
  graph = [[] for _ in range(N+1)]

  for s,e,w in road :
    graph[s].append((w,e))
    graph[e].append((w,s))
  
  result = dijkstra(graph, 1, K)
  return result
  
def dijkstra (graph, startNode, K) : 
  dp = [float('inf')] * (len(graph))
  dp[startNode] = 0
  
  pq = [[0, startNode]]
  while pq :
    dist, node = heappop(pq)
    if dp[node] > dist : continue
    
    for nDist, nNode in graph[node] :
      totalDist = dist + nDist
      if totalDist > K : continue
      if dp[nNode] > totalDist :
        dp[nNode] = totalDist
        heappush(pq, [totalDist, nNode])
    
  return len([v for v in dp if K >= v])