| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | 31 |
- Backjoon
- sort
- Python
- SW역량테스트
- 자바스크립트
- kakao
- 카카오
- Blind
- 코딩테스트
- boj
- 힙큐
- 파이썬
- 그래프
- SSAFY
- SWEA
- algorithm
- 프로그래머스
- 알고리즘
- 완전탐색
- 다이나믹프로그래밍
- 삼성
- DP
- 코테
- 싸피
- BFS
- DFS
- 자료구조
- 스택
- javascript
- 백준
- Today
- Total
목록최소비용 구하기 (2)
맞왜틀
🤔문제 해결 G5 | 다익스트라 정말 기본적인 다익스트라 문제! 따로 키 리스트를 설정하지 않아도 쉽게 풀 수 있다. 💻소스 코드 import sys import heapq input = sys.stdin.readline def dijkstra(s, e): pq = [] heapq.heappush(pq, (0, s)) # 출발지로 가는데 0원의 비용 visited = [0] * (N + 1) while pq: cost, w = heapq.heappop(pq) if w == e: return cost if visited[w]: continue visited[w] = 1 for newt_w, next_cost in adj[w]: if not visited[newt_w]: heapq.heappush(pq, (..
🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..