Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 카카오 코테
- 백준 #백준알고리즘 #알고리즘 #코딩테스트 #코딩테스트준비 #코테준비 #백준2110 #python #문제풀이
- 백준 #백준2217 #백준로프 #python
- 백준 #이거다시풀기
- 그리디알고리즘 #그리디 #백준 #우선순위큐 #최소힙 #최대힙 #알고리즘 #코딩테스트 #python
- 카카오 #프로그래머스 #python #코딩테스트 #오픈채팅방
- 프로그래머스 #python #2021카카오 #카카오코테 #카카오인턴쉽
- 프로그래머스 #python #코딩테스트 #코테공부 #알고리즘 #dict
- 프로그래머스 #c++ #코딩테스트
- 프로그래머스 #네트워크 #c++ #코딩테스트 #코테 #코테준비 #dfs
- 프로그래머스 #NULL 처리하기
- 프로그래머스 #sql #mysql #코딩테스트
- 동
Archives
- Today
- Total
say repository
프림 알고리즘 본문
728x90
최소 신장 트리 (MST)을 구할 경우
1. 크루스칼 알고리즘 (union find 활용)
2. 프림 알고리즘
프림 알고리즘
1. 우선순위 큐 ( heapq ) 활용
2. 우선순위 큐에 (가중치, 시작점) push
3. 간선-1 만큼 우선순위큐 pop
import heapq
# MST (최소 신장 트리 )
# 1. 크루스칼 알고리즘 ( UNION FIND 알고리즘)
# 2. 프림 알고리즘
# 프림 알고리즘
def prim(start):
visited = [False]*(n+1) # 방문처리
sum_w = 0
# 우선순위큐 (가중치, 시작점)
heap = []
heapq.heappush(heap,(0,start))
cnt = 0
while heapq and cnt<n: # 간선-1 만큼 우선순위큐 pop
w,v = heapq.heappop(heap)
if not visited[v]:
visited[v] = True
sum_w += w
cnt += 1
for i in graph[v]:
heapq.heappush(heap,i)
'알고리즘' 카테고리의 다른 글
유니온파인드 알고리즘 (0) | 2025.03.24 |
---|