[백준/G5] 최소비용구하기

 

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

 

다익스트라를 안 풀다 보니 (+파이썬으로 풀다보니) 구현중에 정말 많은 부분을 틀렸다...

import sys
input = sys.stdin.readline
import heapq as hq

MAX = 9999999999 

N = int(input())
M = int(input())

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

for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

dist = [MAX] * (N+1)

start, end = map(int, input().split())
dist[start] = 0

q = []
# (비용, 노드) 순서로 넣기
hq.heappush(q, (0, start))

def dijkstra():
    while q:
        # (비용, 노드) 순서로 받기
        curCost, curNode = hq.heappop(q)
        
        # 이미 더 짧은 경로가 발견된 경우 건너뛰기
        if curCost > dist[curNode]:
            continue
        
        for nextNode, nextCost in graph[curNode]:
            newCost = dist[curNode] + nextCost
            
            if newCost < dist[nextNode]:
                dist[nextNode] = newCost
                # (비용, 노드) 순서로 넣기
                hq.heappush(q, (newCost, nextNode))

dijkstra()
print(dist[end])

 

1. float('inf') 기억 안나서 대충 MAX 욱여넣기

2. graph 리스트 선언할 때 크기 설정 실수하기

3. q 습관적으로 deque로 선언하기

4. 힙큐인데 popleft로 빼기

5. 비용이 적은 순으로 정렬해야 하니 비용이 앞에 와야하는데 노드 - 비용 순으로 넣기

6. visit 배열을 써야 하나 고민하기 -> 최소 비용부터 처리하므로 한번 처리된 노드는 확정된 최단 거리임

7.  for문 안 로직 헷갈리기

 

 

.... 다익스트라의 개념 문제 그 이상 그 이하도 아닌데

역시 알고리즘은 한두달만 안 풀어도 치명적인 것 같다.