프로그래머스 파이썬 배달
https://programmers.co.kr/learn/courses/30/lessons/12978
코딩테스트 연습 - 배달
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4
programmers.co.kr

다익스트라 그 자체
다익스트라를 내가 설명하기엔 좀 그러니 참고 사이트
https://m.blog.naver.com/ndb796/221234424646
23. 다익스트라(Dijkstra) 알고리즘
다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐...
blog.naver.com
우선 1에서 출발하고 나서 최소값을 구해야하기떄문에 비교할 숫자
INF라는 숫자를 DP에 전부 저장한 후
INF = sys.maxsize
dp=[INF]*(N+1)
heap큐를 담을 heap , road값을 저장할 city를 구현해야함.
city에는 road의 가중치 , 이동할 도시 를 순서로 넣어줬음.
heap=[]
city=[[] for i in range(N+1)]
for i in road:
city[i[0]].append((i[2],i[1]))
city[i[1]].append((i[2],i[0]))
다익스트라 알고리즘을 본격적으로 시작
최소값을 담을 dp[start]는 출발지점이기 때문에 0으로 설정하고
heap에 (0과,start)를 담아낸다.
def dijkstra(start):
dp[start] = 0
heapq.heappush(heap,(0,start))
while heap로 힙이 끝날떄까지 반복한다.
heap 안에 있는 가중치와 노드를 꺼내오고나서
dp[노드]가 가중치보다 크다면 이라면 무시하고 다음 스텝으로 가면된다.
아니라면 city[노드]의 값을 꺼내와서 현재 가지고있는 가중치에 값을 더하고 그 더한값이
dp[(이동할 노드)] 보다 작다면 dp의 값은 그 값으로 바뀜.
또한 heap에 현재 내가있는 가중치와 노드를 다시 집어넣고
현재까지의 행동을 다시 반복
def dijkstra(start):
dp[start] = 0
heapq.heappush(heap,(0,start))
while heap:
a, now = heapq.heappop(heap)
if dp[now] < a:
continue
for w, node in city[now]:
next_a = a + w
if next_a < dp[node]:
dp[node] = next_a
heapq.heappush(heap,(next_a,node))
1부터 시작하기 때문에 1부터 설정하고 dp값을 뽑고나서 K값보다 작다면 카운터에 올려 반환하면 끝이다.
하지만 문득 궁금해진게 x<= result <= y 라면 어떻게 해야할까? 라는 생각에 알아보니 bisect 이라는 함수가 있어
활용하였다.
dijkstra(1)
dp.sort()
def cnt(a,left,right):
r = bisect_right(a,right)
l = bisect_left(a,left)
return r-l
return cnt(dp,0,K)
현재 적어놓은 코드는 0과 K안에 들어있는 값을 전부 구하는 함수이다.
전체 코드
import sys
import heapq
from bisect import bisect_left, bisect_right
def solution(N, road, K):
INF = sys.maxsize
dp=[INF]*(N+1)
heap=[]
city=[[] for i in range(N+1)]
for i in road:
city[i[0]].append((i[2],i[1]))
city[i[1]].append((i[2],i[0]))
def dijkstra(start):
dp[start] = 0
heapq.heappush(heap,(0,start))
while heap:
a, now = heapq.heappop(heap)
if dp[now] < a:
continue
for w, node in city[now]:
next_a = a + w
if next_a < dp[node]:
dp[node] = next_a
heapq.heappush(heap,(next_a,node))
dijkstra(1)
dp.sort()
def cnt(a,left,right):
r = bisect_right(a,right)
l = bisect_left(a,left)
return r-l
return cnt(dp,0,K)
쓸데없이 설명을 길게적어놨는데 다른 사람의 코드를 보는게 더 좋을듯 하다 ㅎ.