[알고리즘] 백준 1916 최소비용 구하기 (다익스트라)

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

처음에는 Queue를 이용해서 bfs를 진행하며, 각 노드까지의 거리를 누적한 뒤 마침내 B라는 도착점에 도착했을때 발생할 수 있는 여러 경로의 비용 중 가장 최소값을 탐색이 끝난 뒤 출력하는 식으로 구현하였다.

import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

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

for _ in range(M):
    a, b, cost = map(int, sys.stdin.readline().split())
    graph[a].append([b, cost])

A, B = map(int ,sys.stdin.readline().split())

queue = deque()

min = sys.maxsize
def bfs(start, cost):
    global B, min

    queue.append([start, cost])

    while queue:
        popped = queue.popleft()
        p_start = popped[0]
        p_total_cost = popped[1]
        for i in graph[popped[0]]:
            queue.append([i[0], p_total_cost + i[1]])
        if p_start == B:
            if min > p_total_cost:
                min = p_total_cost

bfs(A, 0)
print(min)

답은 모두 올바르게 나왔지만, 모든 경우의 수를 다 탐색하며 비용을 비교하기 때문인지 메모리 초과가 발생하였다...

이 코드에서 메모리를 어디를 개선해야할지 찾기가 어려워, 블로그를 찾아보니 다익스트라 알고리즘 을 사용해 풀어야 한다고 한다.

다익스트라 알고리즘을 적용하기 위해서는 일반 queue가 아닌 priority queue를 이용해, 인접 노드를 비용순으로 정렬하고 비용이 적게 드는 노드를 우선으로 탐색을 진행한다.

그리고 해당 노드에 도착했을때 까지 드는 비용을 costs라는 리스트에 따로 저장한 뒤, 이후 탐색에서 다른 경로에서 해당 노드까지 드는 비용이 기존에 저장되어 있는 비용보다 더 많이 든다면, 해당 경로를 고려하지 않고 넘기는 방식으로 구현하게 된다.

이렇게 구현하게 되면, 처음 코드처럼 B라는 도착지에 도착할 수 있는 모든 경로의 비용을 찾고 비교하지 않아도되기 때문에 연산 횟수를 상당히 줄일 수 있다.

아래는 다익스트라와 우선순위큐를 이용해 메모리 초과를 개선하여 정답을 받은 코드이다.

import heapq
import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

# 노드 간의 연관관계와 소비되는 비용을 저장하는 2차원 리스트
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b, cost = map(int, sys.stdin.readline().split())
    graph[a].append([cost, b])

A, B = map(int ,sys.stdin.readline().split())

# 인덱스에 해당하는 노드까지 걸리는 최소 비용을 저장하는 리스트
costs = [sys.maxsize for _ in range(N + 1)] 

min = sys.maxsize
def bfs(start, cost):
    global B, min
    queue = []
    # 우선순위큐에서 비용순 정렬을 위해 [비용, 출발노드번호] 순으로 정렬해준다.
    # 첫 시작점에서는 제자리로 비용이 들지 않으므로 비용은 0이다.
    heapq.heappush(queue, [cost, start])

    while queue:
        popped = heapq.heappop(queue)
        p_start = popped[1] # 현재 노드 번호
        p_total_cost = popped[0] # 이 노드 까지 걸리는 비용
        
        # 현재 노드까지의 최소비용보다 새롭게 탐색되어 갱신되어있는 현재 비용이 더 크다면, 
		# 해당 경로는 고려하지 않고 넘긴다.
        if costs[p_start] < p_total_cost:
            continue
		
        # 기록 되어있는 최소 비용보다 덜 걸린다면, 해당 노드의 다음 인접 노드를 탐색한다.
        for i in graph[p_start]:
        	# 마찬가지로 다음 노드 까지의 최소 비용이, 
            # 현재 노드에서 다음 노드 가는 비용을 더한 것보다 크다면, 해당 노드 경로를 무시하고
            # 작다면, 새롭게 리스트를 갱신하고 다음 노드를 탐색할 수 있도록 우선순위큐에 넣어준다.
            if costs[i[1]] > p_total_cost + i[0]:
                costs[i[1]] = p_total_cost + i[0]
                heapq.heappush(queue, [p_total_cost + i[0], i[1]])

bfs(A, 0)
# 최종 도착지 인덱스의 비용을 출력한다.
print(costs[B])