(Python/파이썬) - 프로그래머스 : 배달

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

코딩테스트 연습 - 배달

---

• 문제 : 

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

 

---

• 풀이 :

최단경로를 찾는 알고리즘 중 1번 마을에서 나머지 마을로 가는 최단경로를 찾는 문제이고, 가중치가 있는 그래프이므로 다익스트라 알고리즘으로 해결했습니다.

1번 마을에서 다른 마을로 가는 가중치와 도착지를 minheap에 넣고 가중치가 낮은 마을부터 탐색을 실시했습니다. 

현재 마을까지의 가중치가 heap에 넣을 시점의 가중치(cost)보다 작을 경우 탐색을 실시하지 않고(15~16라인)

아닌 경우에만 totalCost를 계산해주어 다음 마을로 가는 방법이 최단경로인지 여부를 확인해주었습니다.

 

처음에 1번마을 제자리로 배달하는 경우를 고려 안해서 한 번 틀렸는데 1번마을에서 1번마을로 가는 경우는 가중치가 0 입니다. (안 움직여도 되므로)

 

 

---

• 소스코드 : 

import heapq as hq
 
def solution(N, road, K):
    answer = 0
    graph = [[] for _ in range(N+1)]
    distance = [float("inf") for _ in range(N+1)]
    distance[1] = 0
    for start,end,cost in road:
        graph[start].append([end,cost])
        graph[end].append([start,cost])
    heap  = []
    hq.heappush(heap,(0,1))
    while heap:
        cost,curr = hq.heappop(heap)
        if distance[curr] < cost:
            continue
        for nxt,c in graph[curr]:
            totalCost = cost + c
            if totalCost < distance[nxt]:
                distance[nxt] = totalCost
                hq.heappush(heap,(totalCost,nxt))
    for i in distance[1:]:
        if i <= K:
            answer += 1
    print(distance)
    return answer