[BOJ] 1916. 최소비용 구하기

⏱️ 소요시간

1시간 이하. 다익스트라를 학습하고나서 바로 풀은 문제라 빨리 풀었습니다. 그냥 풀었으면 지금 실력에서는 이 문제가 다익스트라인가? 라는 고민을 했을지는.. 연습이 좀 더 필요하다 !

📚 문제 요약

[백준] 1916. 최소비용 구하기
마을과 버스의 수를 입력으로 받고, 마을 -> 마을까지의 cost가 주어진다. 시작과 도착점을 알려줬을 때 갈 수 있는 최소 비용을 출력 (시작~도착까지는 반드시 갈 수 있다)

📑 풀이 요약

시작, 도착점이 주어졌고, 비용은 양수로 주어졌다. 두 점 사이의 거리를 구하는 문제는 최소비용문제 이며, 각 경로 당 비용이 다르기 때문에 다익스트라 알고리즘을 이용하여 해결할 수 있다.

🌟 내가 만난 어려웠던 점

시간 초과 문제

input을 sys.stdin.readline을 이용하여 해결함.
for문에서 반복의 횟수가 많아지면 input이 아니라 sys.stdin.readline을 이용하여 입력받자

메모리 초과 문제

다익스트라를 구현할 때 현재 cost의 비용과 갱신할 cost 비용을 비교하여, 갱신할 cost가 더 작을 때 우선순위큐에 넣어야 하는데 작거나 같을 때 넣어 불필요한 연산 횟수가 증가하였고 메모리 초과로 이어짐

🖥️ 전체 코드

import sys 
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
n = int(input()) #도시 개수
m = int(input()) #버스 개수
INF = 1e9 #최대 비용
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
dist = [0]+ [INF for _ in range(n)]

#1. 그래프 초기화
for i in range(m):
    start, end, cost = map(int, input().split())
    if cost < graph[start][end]:
        graph[start][end] = cost
for i in range(1, n):
    graph[i][i] = 0
start, end = map(int, input().split())

#2. cost, 시작점
def dijkstra(start):
    heap = [(0, start)] #초기화 과정
    visited[start] = True
    heapify(heap)
    dist[start] = 0

    while heap:
        cost, city = heappop(heap)
        visited[city] = True
        if city == end: #도착점인 경우
            break
        for i in range(1, n+1):
            if not visited[i]: #방문한 적 없고
                if cost+graph[city][i] < dist[i]:
                    dist[i] = cost+graph[city][i]
                    heappush(heap, (dist[i], i))
        #print(dist)
    print(dist[end])