[알고리즘]백준 1916 : 최소비용 구하기 (파이썬)

ssh00n·2023년 3월 19일
0

1916번: 최소비용 구하기

문제

  • N개의 도시(vertices), M개의 버스(edges) 및 비용(costs)
  • 출발 도시(start)에서 도착 도시(end)까지 가는데 드는 최소 비용 구하기

접근

최소비용 구하는 문제이므로 큐를 이용하여 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문을 확인하다 보니 시간복잡도가 매우 높아진다.

위 두 방식으로는 어떻게 개선하여도 통과하기 어렵다고 생각하여 질문 게시판을 보니 모두 다익스트라 알고리즘에 대해 말하고 있었다.

다익스트라 알고리즘(Dijkstra’s Algorithm)

다익스트라 알고리즘은 다이나믹 프로그래밍(Dynamic Programming, DP)을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 이 때 경로에는 음의 간선을 포함할 수 없다. 다익스트라 알고리즘이 DP인 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.

작은 문제가 큰 문제의 부분집합에 속해있고, 두 문제가 같은 모양이 아니기 때문에 분할 정복(Divide-Conquer)이 아닌 DP인 것이다.

다익스트라를 1916 : 최소비용 구하기 문제에 적용하는 과정은 다음과 같다.

  1. 출발지(start)를 기준으로 각 노드의 최소 비용을 저장
  2. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택
  3. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신
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문 첫번째 줄부터

  1. 현재 노드(a)까지 오는 데 누적되었던 비용이(cur_cost) 다른 길을 통해서 구한 최소 비용(costs[cur_v])보다 크다면 continue로 다음 반복으로 넘어간다.

  2. 현재 노드에서 다음 노드로 이동하는 데 비용을 더한 값이 그동안 계산된 costs[nest_v]보다 크다면 continue로 다음 반복으로 넘어간다.

  3. (1, 2)에 해당하지 않은 경우, 즉 현재 노드(a)까지 오는 비용이 최소이고, 다음 노드로 이동하는 비용을 더한 값이 그동안 계산되어왔던 costs[next_v]보다 작다면 이를 갱신하고, 계산된 값을 힙에 push한다.

profile
Whatever I want

2개의 댓글

comment-user-thumbnail
2023년 3월 19일

너무 이해가 잘 됩니다!!! 감ㅅ가합니다!!

1개의 답글