[프로그래머스] 12978 파이썬 - 배달

풀이

문제를 읽어보면 1번 마을에서 다른 마을까지 거리 중 최단 거리를 구하는 문제임을 알 수 있었다.

 

이때, 제한사항을 읽어보니 노드(마을의 개수)가 최대 50개임을 알 수 있었다.

따라서 다익스트라 알고리즘을 사용하여 풀 수 있는 문제였다.

 

다익스트라 알고리즘

CT-Study/PART 2/Chapter 9, 최단 경로.md at master · JeongEunJi1127/CT-Study

- 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘
- 가장 비용이 적은 노드를 선택한다
- 그리디 알고리즘으로 분류된다
- 음의 간선이 없을 때 정상적으로 동작한다
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이 다익스트라 알고리즘!

다익스트라 최단 경로 알고리즘 시간복잡도 (V = 노드의 개수) : O(V^2)

다익스트라 최단 경로 알고리즘의 원리
1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 위 과정 중 3, 4번을 반복

 

코드

import heapq 

def solution(N, road, K):
    answer = 0
    distance = [int(1e9)] * (N+1)
    graph = [[] for _ in range(N+1)] 
    
    # 노드의 개수 최대 50개 -> 다익스트라 알고리즘 사용
    for i in road:
        start, end, d = i
        graph[start].append((d,end))
        graph[end].append((d,start))
    
    dijkstra(1, distance, graph)
    
    for i in range(1,len(distance)):
        if distance[i] <=K:
            answer +=1
    return answer

def dijkstra(start, distance, graph):
    heap = []
    heapq.heappush(heap,[0,start])
    distance[start] = 0
    
    while heap:
        dist, now = heapq.heappop(heap)
        # 현재 거리가 더 작으면 무시
        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(heap,(cost,i[1]))

 

 

프로그래머스