[프로그래머스][C++] 배달

 

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

코딩테스트 연습 - 배달

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

 

이 문제는 무조건 다익스트라(dijkstra) 알고리즘을 사용해서 풀 수 있음.

DFS를 사용해서 풀이하니 시간초과가 발생해서 결국 풀이를 보고

다익스트라(dijkstra) 알고리즘을 배워서 풀이함.

 

import heapq



def dijkstra(start, link, N):

    result = [1e9] * (N+1)
    result[start] = 0
    heap = []
    heapq.heappush(heap, (start, 0))
    while heap :
        destination, distance = heapq.heappop(heap)
        if result[destination] < distance:
            continue

        for des, dis in link[destination]:
            nextDistance = distance + dis
            if nextDistance < result[des]:
                result[des] = nextDistance
                heapq.heappush(heap, (des, nextDistance))
    return result



def solution(N, road, K):
    answer = 0
    link = [[]for _ in range(N+1)]
    for x, y, z in road:
        link[x].append((y, z))
        link[y].append((x, z))

    result = dijkstra(1, link, N)

    for distanceResult in result:
        if distanceResult <= K:
            answer+=1

    return answer

꾸준히 하다보면 실력이 늘겠지..