[백준] 1916 - 최소 비용 구하기 (다익스트라)

 

 

1️⃣  - 처음 생각한 코드

1.  그래프에 경로를 전부 저장
2.  bfs로 시작지점부터 경로 시작해서 이전 경로까지 거리를 계속 비교해가면서 더 작은 값을 저장
3. 반복해서 마지막 최종 목적지 배열의 값 출력

 

from sys import stdin as s
from collections import deque
import heapq

s = open('input.txt','rt')

N = int(s.readline())
M = int(s.readline())

graph = {}

for _ in range(M):
    start, end , dis = list(map(int,s.readline().split()))
    graph[start] = graph.get(start,[]) + [(dis,end)]


start , end = list(map(int,s.readline().split()))


def BFS(start):
    q = deque()
    q.append((0,start))
    distance = [int(1e9)] * (N+1)
    distance[start] = 0


    while q:
        dist, a = q.popleft()
        if distance[a] < dist:
            continue
        if graph.get(a) != None:
            for e,i in graph[a]:
                if distance[i] > e+distance[a]:
                    distance[i] = min(e + distance[a],distance[i])
                    q.append((distance[i],i))

    return distance
            

dist_start = BFS(start)

print(dist_start[end])

 

 

2️⃣ - 참고한 코드를 바탕으로 수정

아무리봐도 로직은 다른 사람들이랑 거의 똑같아서 뭐가 문제인지 찾고 찾다가

graph = {} 

이 부분을 딕셔너리로 받는게 편해서 그렇게 사용하고 있었는데, 이 부분을 배열로 변경하니까 바로 해결이 됐다. 🥲

이 문제에서는 큐를 쓰든 우선순위 큐를 쓰든 둘 다 정답으로 출력되는 것을 확인했다.

from sys import stdin as s
import heapq

s = open('input.txt','rt')

N = int(s.readline())
M = int(s.readline())

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

for _ in range(M):
    start, end , dis = list(map(int,s.readline().split()))
    graph[start].append((dis,end))


start , end = list(map(int,s.readline().split()))


def BFS(start):

    distance = [int(1e9)] * (N+1)
    pq = []
    heapq.heappush(pq,(0,start))
    distance[start] = 0

    while pq:

        d, x = heapq.heappop(pq)

        if distance[x] < d:
            continue
        

        for nw, nx in graph[x]:
                nd = d + nw
                if distance[nx] > nd:
                    heapq.heappush(pq,(nd,nx))
                    distance[nx] = nd

    return distance
            

dist_start = BFS(start)

print(dist_start[end])