[백준]1916 최소 비용 구하기(Python)

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

문제 접근

 

1753 최단경로 문제풀이를 참고해서 풀었다.

다만 입력받은 시작점(s)로 다익스트라 알고리즘을 실행하여 dp에 최소 비용을 저장하고 그에 해당하는 dp[e]를 출력한다.

 

**이코테 pg239~

heapq 라이브러리 (거리, 노드번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 거리순으로 정렬

 

힙에 N개의 데이터를 넣고, 모두 빼는 과정은 O(NlogN)

E개의 간선을 넣고, 모두 빼는 과정은 O(ElogE)

항상 E <= V^2 

다익스트라의 시간 복잡도: O(ElogV) 

 

코드

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize

# 도시의 개수
N = int(input())
# 버스의 개수
M = int(input())

dp = [INF] * (N+1)
graph = [[] for _ in range(N+1)]


def Dijkstra(start):
    heap = []
    dp[start] = 0   # 시작 노드로 가기 위한 최단 경로는 0
    heapq.heappush(heap, (0, start)) # (거리, 노드번호) => 거리는 우선순위

    while heap: # 힙에 원소가 없을 때까지 반복
        wei, now = heapq.heappop(heap)  # 가장 우선 순위가 높은(거리가 짧은) 노드에 대한 가중치, 노드번호 pop

        if dp[now] < wei:   # 현재 노드가 이미 처리 적이 있는 노드라면 무시(중요!!) => 큐에 계속 쌓이기 때문에
            continue

        for w, next_node in graph[now]: # 현재 노드와 연결된 다른 인접한 노드들을 확인하는 과정
            next_wei = w + wei

            if next_wei < dp[next_node]:    # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 dp 갱신, 우선순위 큐에 삽입 
                dp[next_node] = next_wei
                heapq.heappush(heap, (next_wei, next_node))


for _ in range(M):
    s, e, w = map(int, input().split())
    graph[s].append((w,e))  # (가중치, 목적지) 형태로 저장

s, e = map(int, input().split())
Dijkstra(s)
print(dp[e])

 

문제 회고

 

벨만-포드, 플로이드-워셜만 하다보니 다익스트라 알고리즘에 소홀했다.

스터디 전 다시 복습하도록...(완료!!)