[백준] 최소비용 구하기 - Python 파이썬

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

사용개념: 다익스트라

 

가중치를 갖는 그래프에서 최단 경로를 찾는 문제이므로 다익스트라 알고리즘을 사용해 해결한다.

 

그래프 입력 받기

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

for _ in range(M):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))

 

입력 결과)

[[], [(2, 2), (3, 3), (4, 1), (5, 10)], [(4, 2)], [(4, 1), (5, 1)], [(5, 3)], []]

 

다익스트라 알고리즘

def dijkstra(graph, start):
    # 모든 노드의 거리를 무한대로 초기화
    distances = [float('infinity')] * (N+1)
    distances[start] = 0
    # 우선순위 큐
    queue = []
    # 시작 노드부터 탐색 시작
    heapq.heappush(queue, [distances[start], start])
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        # 기존 거리보다 크면 무시
        if distances[current_node] < current_distance:
            continue
        
        # 인접 노드 탐색
        for adjacent, weight in graph[current_node]:
            distance = current_distance + weight
            
            # 더 짧은 경로 있으면 업데이트
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
    
    return distances

 

 

전체코드

import heapq

def dijkstra(graph, start):
    # 모든 노드의 거리를 무한대로 초기화
    distances = [float('infinity')] * (N+1)
    distances[start] = 0
    
    # 우선순위 큐
    queue = []
    
    # 시작 노드부터 탐색 시작작
    heapq.heappush(queue, [distances[start], start])
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        # 기존 거리보다 크면 무시
        if distances[current_node] < current_distance:
            continue
        
        # 인접 노드 탐색
        for adjacent, weight in graph[current_node]:
            distance = current_distance + weight
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
    
    return distances

N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))
start, end = map(int, input().split())
dist_result = dijkstra(graph, start)
print(dist_result[end])

 

그래프 입력 받은게 영 지저분해서.. 쓸데없지만 딕셔너리로 입력 받을 수도 있다

입력 받기

graph = {i: {} for i in range(1, N + 1)}

for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a][b] = w

 

결과)

{1: {2: 2, 3: 3, 4: 1, 5: 10}, 2: {4: 2}, 3: {4: 1, 5: 1}, 4: {5: 3}, 5: {}}

 

나머지 코드

import sys
import heapq
input = sys.stdin.readline

def dijkstra(graph, start, end):
    distances = {node: float('inf') for node in range(1, N + 1)}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [0, start])
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if current_node == end:
            return current_distance
            
        if distances[current_node] < current_distance:
            continue
            
        for next_node, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[next_node]:
                distances[next_node] = distance
                heapq.heappush(queue, [distance, next_node])
                
    return distances[end]

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

graph = {i: {} for i in range(1, N + 1)}

for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a][b] = w

start, end = map(int, input().split())
print(dijkstra(graph, start, end))