배달

프로그래머스

 

전형적인 최단 거리 문제.

다익스트라 알고리즘을 활용해서 풀었다.

 

---

풀이 코드

import heapq

INF = int(1e9)

# 다익스트라(O(ElogV))
def dijkstra(start, N, road):
    q = []
    distance = [INF] * (N+1)
    graph = [[] for _ in range(N+1)]
    
    # 데이터 입력
    for r in road:
        a, b, c = r[0], r[1], r[2]
        graph[a].append((b, c))
        graph[b].append((a, c))
        
    # 출발 좌표 큐에 넣기
    heapq.heappush(q, (0, start))
    # 출발 좌표 거리는 0
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        
        # now까지의 거리가 이미 최단 거리인 경우(이미 처리된 경우)에는 다음으로 넘어감
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1] # cost: now를 거쳐서 i[0]까지 가는 비용
            if cost < distance[i[0]]: # now를 거쳐서 i[0]까지 가는 비용이 현재 distance 리스트에서 start -> i[0] 비용보다 작은 경우
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0])) # 다시 큐에 추가
    
    return distance
        
        
def solution(N, road, K):
    answer = 0
    
    distance_list = dijkstra(1, N, road)
    
    for i in range(1, N+1):
        if distance_list[i] <= K:
            answer += 1

    return answer