백준, 최소 비용 구하기

백준, 최소 비용 구하기

 

📜문제

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

1916번: 최소비용 구하기

 

분류 : accepted

 

❌ 초기 접근법

시작점에서 마지막점까지 도달할 모든 경로에 대한 비용을 탐색해 total_costs 리스트에 저장.

결과값으로 total_costs의 최솟값을 반환한다.

total_costs = []

def move(start, end):
    queue = deque([(start, 0)])
    # visited = set([start])

    while queue:
        cur_node, cost = queue.popleft()

        if cur_node == end:
            total_costs.append(cost)
        for neighbor in adj[cur_node]:
            # if neighbor not in visited:
                # visited.add(neighbor)
                queue.append((neighbor, cost + costs[cur_node][neighbor]))

move(s, e)
print(min(total_costs))

메모리 제한이 128MB로 메모리초과 발생

풀이법을 찾아보니, 다익스트라.. 예전에 이해하지 못했었다.

당시 같은 팀원이 열심히 설명해줬는데도 내가 이해하지 못했었다..

그런데 참 신기하게도 이번에 공부하면서 이해가 됐다.

 

시작점에서 각 노드에 도달하기 까지 걸리는 최소 비용을 costs 리스트에 업로드하면서 탐색하면 된다.

 

 

✅ 코드

import heapq

# N = 5
# M = 8
N = int(input())
M = int(input())

graph = {x:[] for x in range(1,N+1)}
for _ in range(M):
    s, e, c = map(int, input().split())
    graph[s].append((e, c))
# graph = {1: [(2, 2), (3, 3), (4, 1), (5, 10)], 2: [(4, 2)], 3: [(4, 1), (5, 1)], 4: [(5, 3)], 5: []}

# start, end = 1, 5
start, end = map(int, input().split())

costs = [float("inf")] * (N+1)

def dijkstra(start):
    hq = [(0, start)] # cost, node

    while hq:
        cost, node = heapq.heappop(hq)

        if costs[node] < cost:
            continue
        for next_node, bus_cost in graph[node]:
            new_cost = cost + bus_cost
            if costs[next_node] > new_cost:
                costs[next_node] = new_cost
                heapq.heappush(hq, (new_cost, next_node))

dijkstra(start)
print(costs[end])