[프로그래머스] 배달

1. 문제

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

 

2. 코드

python 1

import heapq

def get_shortest_dist(graph, start, n):
    dist = [float('inf')] * (n+1)
    heap = []
    
    dist[start] = 0
    heapq.heappush(heap, (0, start))

    while heap: 
        current_dist, current_node = heapq.heappop(heap)

        if dist[current_node] < current_dist:
            continue

        for next_node, time in graph[current_node]:
            new_dist = dist[current_node] + time

            if dist[next_node] > new_dist:
                dist[next_node] = new_dist
                heapq.heappush(heap, (new_dist, next_node))

    return dist

def solution(N, road, K):
    answer = 0
    graph = [[] for _ in range(N+1)]
    
    # 그래프 양방향
    for start, end, time in road:
        graph[start].append((end, time))
        graph[end].append((start, time))
    
    distance = get_shortest_dist(graph, 1, N)
    
    for i in range(1, N + 1):
        if distance[i] <= K:
            answer += 1
    return answer

풀이

1. graph 생성
2. graph를 양방향으로 값을 저장
3. 최단 거리 탐색(get_shorteest_dist 함수)
   1. dist 생성 → 무한대 값
   2. 시작점, time = 0 에서 시작
   3. while heap
      1. heap에서 가장 짧은거리 노드(current_node) 꺼냄
      2. 이미 처리된 거리보다 현재 처리가 크면 → 무시함
      3. 연결된 다음 노드 확인하며 → 현재까지 거리 + 이동 시간 이 기존 기록보다 짧으면 dist 갱신하고 heap넣음
4. 1에서 각 n번 마을까지의 최단 거리가 k이하인 모든 마을 수를 출력

 

3. 메모

• 시간 복잡도: O(ElogV)
• 다익스트라 사용
• 다익스트라 알고리즘을 사용하면 무난하게 풀 수 있음
• 1번 마을도 포함해야 함