프로그래머스 배달

접근 방식(알고리즘 분류)

• 다익스트라

내 풀이

import heapq

def solution(N, road, K):

    graph = [[] for _ in range(N+1)]
    for i in road:
        graph[i[0]].append((i[2], i[1]))
        graph[i[1]].append((i[2], i[0]))

    distance = [1e9] * (N+1)
    def dijkstra(start):

        q = []
        heapq.heappush(q, (0, start))
        distance[start] = 0
        while q:
            dist, now = heapq.heappop(q)
            if distance[now] < dist:
                continue

            for i in graph[now]:
                cost = dist + i[0]
                if cost < distance[i[1]]:
                    distance[i[1]] = cost
                    heapq.heappush(q, (cost, i[1]))
        result = 0
        for i in distance:
            if i <= K:
                result += 1
        return result
    answer = dijkstra(1)

    return answer

풀이 설명

• 기본적인 다익스트라 문제였다.
• 양방향으로 이어져 있다는 것을 유의해야한다.
• cost = dist + i[0] 에서 처음에는 dist + distance[i[1]]로 착각했다.

느낀점

• 눈으로 볼 때랑 직접 풀때랑 차이가 심하다는 것을 다시한번 느꼈다.