최소비용 구하는 문제이므로 큐를 이용하여 BFS로 탐색하면서 cost를 갱신하고, 도착점에 이르렀을 때 누적된 비용을 확인하고 min_cost를 갱신하고자 했다.
→ 비효율적인 접근이다. 같은 노드를 여러번 방문하며 최소 비용을 갱신해야 하므로 큐에 같은 노드가 계속해서 enque 된다.
import sys
from collections import deque
# 메모리 초과
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b, cost = map(int, input().split())
graph[a].append([b, cost])
start, end = map(int, input().split())
def bfs(start):
min_cost = 1e7
q = deque()
q.append([start, 0])
while q:
cur_v, cur_cost = q.popleft()
if cur_v == end and cur_cost < min_cost:
min_cost = cur_cost
for v, c in graph[cur_v]:
q.append([v, cur_cost+c])
return min_cost
print(bfs(start))
해당 코드는 메모리 초과가 발생했다.
작성한 코드에는 도시까지의 비용이 같은 경우에 큐에 여러번 들어가는 문제가 있었다.
ex) 도시 4 까지 가는 방법이 여러개이고 그 비용이 같은 경우 1→ 4(4), 1→2→4 (4)
import sys
from collections import deque
# 시간 초과
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b, cost = map(int, input().split())
graph[a].append([b, cost])
start, end = map(int, input().split())
def bfs(start):
min_cost = 1e7
q = deque()
q.append([start, 0])
while q:
cur_v, cur_cost = q.popleft()
if cur_v == end and cur_cost < min_cost:
min_cost = cur_cost
for v, c in graph[cur_v]:
if [v, cur_cost+c] in q:
continue
q.append([v, cur_cost+c])
return min_cost
print(bfs(start))
같은 값이 큐에 여러번 들어가는걸 막기 위해, if 문으로 큐에 있는지 확인해주었으나, 이 코드는 시간초과가 발생하였다. 노드에 연결된 정점마다(visited 여부 확인도 없으니) 모두 if문을 확인하다 보니 시간복잡도가 매우 높아진다.
위 두 방식으로는 어떻게 개선하여도 통과하기 어렵다고 생각하여 질문 게시판을 보니 모두 다익스트라 알고리즘에 대해 말하고 있었다.
다익스트라 알고리즘은 다이나믹 프로그래밍(Dynamic Programming, DP)을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 이 때 경로에는 음의 간선을 포함할 수 없다. 다익스트라 알고리즘이 DP인 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.
작은 문제가 큰 문제의 부분집합에 속해있고, 두 문제가 같은 모양이 아니기 때문에 분할 정복(Divide-Conquer)이 아닌 DP인 것이다.
다익스트라를 1916 : 최소비용 구하기 문제에 적용하는 과정은 다음과 같다.
import sys
import heapq
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b, cost = map(int, input().split())
graph[a].append([b, cost])
start, end = map(int, input().split())
costs = [1e9 for _ in range(n+1)]
heap = []
costs[start] = 0
heapq.heappush(heap, [0, start])
while heap:
cur_cost, cur_v = heapq.heappop(heap)
if costs[cur_v] < cur_cost:
continue
for next_v, next_cost in graph[cur_v]:
sum_cost = cur_cost + next_cost
if sum_cost >= costs[next_v]:
continue
costs[next_v] = sum_cost
heapq.heappush(heap, [sum_cost, next_v])
print(costs[end])
전체 노드에 대한 cost를 저장하는 리스트 costs와, 우선순위 큐를 이용한다.
현재 노드(a)에서 다른(b) 노드를 거쳐서 특정 노드(c)에 가는 비용과 현재까지 갱신된 특정 노드(c)까지의 비용을 비교하여, 더 작을 경우 이를 갱신해나가는 과정을 거친다.
while문 첫번째 줄부터
현재 노드(a)까지 오는 데 누적되었던 비용이(cur_cost) 다른 길을 통해서 구한 최소 비용(costs[cur_v])보다 크다면 continue로 다음 반복으로 넘어간다.
현재 노드에서 다음 노드로 이동하는 데 비용을 더한 값이 그동안 계산된 costs[nest_v]보다 크다면 continue로 다음 반복으로 넘어간다.
(1, 2)에 해당하지 않은 경우, 즉 현재 노드(a)까지 오는 비용이 최소이고, 다음 노드로 이동하는 비용을 더한 값이 그동안 계산되어왔던 costs[next_v]보다 작다면 이를 갱신하고, 계산된 값을 힙에 push한다.
너무 이해가 잘 됩니다!!! 감ㅅ가합니다!!