배달

문제이해
N 마을개수
마을의 연결정보가 주어지고 road의 0,1번인덱스 마을끼리 연결 (양방향연결), 2번인덱스는 걸리는시간
1번마을에서 무조건 출발해서 각마을까지의 최소걸리는시간을 구함(다익스트라) -> 이까지가 문제풀이 핵심
여기서 K시간 이하로 걸리는 개수 구하기 

 

 

다익스트라(import heapq)

1. 연결정보로 연결그래프생성하고

2. times = {} 배열(각마을까지의 최소시간배열) 만들고 infinity 로 한후

3. 시작마을의 시간은 0으로 만듬

4. 최소힙생성후 (0,1) # (시간,마을) 을 담고 시작

 

import heapq
def solution(N, road, K):
    answer = 0
    # 다익스트라 (최소비용) costs 만들어서 푸는것
    # 연결정보만들기
    graph = {}
    for a,b,c in road:
        if a not in graph:
            graph[a] = [(c,b)]
        else:
            graph[a].append((c,b))
        if b not in graph:
            graph[b] = [(c,a)]
        else:
            graph[b].append((c,a))
    # return graph {1: [(1, 2), (2, 4)], 2: [(1, 1), (3, 3), (2, 5)],
    times = {node:float('infinity') for node in graph}
    times[1] = 0
    min_heap = [(0,1)] # 현재 시간과 현재 마을
    while min_heap:
        current_time,current_node = heapq.heappop(min_heap)
        if times[current_node] < current_time:
            continue
        for new_time,nei in graph[current_node]:
            time = new_time + current_time
            if time < times[nei]:
                times[nei] = time
                heapq.heappush(min_heap,(time,nei))
    # return times {1: 0, 2: 1, 3: 4, 5: 3, 4: 2}
    for i in times:
        if times[i] <= K:
            answer += 1
    return answer


N = 6 # 마을의 개수
road =  [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]  # 마을 연결정보
# 1 과 2 마을이 연결되어있고 1시간 걸림  ( 마을은 양방향 연결)
K = 4 # 3시간이내로 배달할수 있는 마을의 개수 return
# 시작마을은 무조건 1번 마을
print(solution(N,road,K))