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문 안 로직 헷갈리기
.... 다익스트라의 개념 문제 그 이상 그 이하도 아닌데
역시 알고리즘은 한두달만 안 풀어도 치명적인 것 같다.
'크래프톤정글10기 > 파이썬' 카테고리의 다른 글
| [백준/G4] 탈출 (0) | 2025.09.18 |
|---|---|
| [백준/G4] 빙산 (0) | 2025.09.17 |
| [백준/G2] 가운데를 말해요 (0) | 2025.08.22 |
| [백준/G4] 스도쿠 (1) | 2025.08.18 |
| [백준/G3]소문난칠공주 (2) | 2025.08.16 |