알고리즘/알고리즘 공부(python)

프로그래머스_배달/Using python 파이썬

소소한필통 2022. 6. 21. 16:37

문제

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

 

 

Prolem About

문제 그림

핵심 키워드

각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려

고 합니다.

 

위 문장으로 이뤄 봤을 때 가중치가 각각 다른 그래프 중 최단경로를 구해야 하므로 다익스트라 알고리즘을 써야한다.

 

 

아래의 그림으로 최단경로를 구하는 문제에서 어떤 알고리즘을 써야 하는지 알 수 있다.

출처 메자곰

 

문제 코드

python에서 다익스트라는 구현하기 쉽다. heapq 모듈을 써서 최소비용 지금 갈 수 있는 곳 중에 최소 비용인 거리를 먼저 탐색하면서 안가도 될곳을 안가게 만들게 하면된다.

import heapq
def solution(N, road, K):
    # index를 통해서 간선의 위치를 파악해주기 위해서 list 만들기
    lst = [[] for _ in range(N + 1)]
    # 출바 index애 [cost, 도착index]를 넣어서 list 간선 만들어 주기
    for s, e, c in road:
        lst[s].append([c, e])
        lst[e].append([c, s])
    
    # cost는 최대한 큰 값으로 사용
    inf = int(1e9)
    cost = [inf] * (N + 1)
    
    # 1번에서 출발하므로 cost[1]은 0을 넣고 Q에 (비용, 현재위치) 넣기
    cost[1] = 0
    Q = [(0, 1)]
    
    # heapq를 할용한 다익스트라 구현
    while Q:
        c, n = heapq.heappop(Q)
        if cost[n] == c:
            for go_cost, go in lst[n]:
                now_cost = go_cost + cost[n]
                if cost[go] > now_cost and now_cost <= K:
                    cost[go] = go_cost + cost[n]
                    heapq.heappush(Q, (now_cost, go))
    answer = sum([1 if cost[i] <= K else 0 for i in range(1, N+1)])
    return answer