기타

프로그래머스 파이썬 배달

작지 2021. 12. 6. 23:38

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)

쓸데없이 설명을 길게적어놨는데 다른 사람의 코드를 보는게 더 좋을듯 하다 ㅎ.