힙을 이용한 프림의 MST
하나의 정점에서 트리를 확장합니다
힙을 이용한 프림의 MST은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
MST로 가는 또 다른 경로
프림 알고리즘도 최소 신장 트리를 찾지만, 모든 간선을 먼저 정렬하는 대신 연결된 하나의 덩어리를 바깥쪽으로 확장해 나갑니다. 🌱
한 정점에서 시작해 확장하기
임의의 시작 정점을 선택하고 방문한 것으로 표시합니다. 트리는 하나의 노드에서 시작하여 한 번에 간선 하나씩 확장됩니다.
visited = [False] * n경계선 아이디어
각 단계에서 트리와 바깥쪽을 연결하는 모든 간선을 살펴봅니다. 프림 알고리즘은 이러한 경계 간선 중 항상 가장 저렴한 간선을 선택합니다.
힙으로 최솟값 선택하기
최소 힙을 사용하면 가장 저렴한 경계 간선을 빠르게 찾을 수 있습니다. 후보 간선을 힙에 넣고 매 라운드마다 가장 작은 가중치를 꺼냅니다.
import heapq
heap = [(0, start)]가장 저렴한 간선 꺼내기
힙에서 가장 작은 항목을 꺼냅니다. 그러면 성장 중인 트리에 연결하기 가장 저렴한 가중치와 다음 정점을 얻을 수 있습니다.
w, u = heapq.heappop(heap)오래된 항목 건너뛰기
하나의 정점이 힙에 여러 번 들어갈 수 있습니다. 이미 방문한 정점을 꺼냈다면 무시하고 다시 꺼내면 됩니다.
if visited[u]:
continue추가하고 확장하기
꺼낸 정점을 방문한 것으로 표시하고 그 가중치를 전체 합에 더합니다. 그런 다음 해당 정점에서 나가는 각 간선을 다음 단계를 위해 힙에 넣습니다.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))완성될 때까지 반복하기
모든 정점을 방문할 때까지 계속 꺼내고 확장합니다. 그러면 누적된 전체 합이 최소 신장 트리의 가중치가 됩니다.
실행 시간
각 간선은 한 번 넣고 한 번 꺼낼 수 있으므로 힙 기반 프림 알고리즘은 O(E log V)에 실행되며, 크루스칼 알고리즘과 비슷합니다.
프림과 크루스칼 비교
인접 목록을 사용하는 조밀한 그래프에는 프림 알고리즘을 사용하고, 이미 일반적인 간선 목록이 있다면 크루스칼 알고리즘을 사용하십시오. 두 방법 모두 같은 MST 가중치를 얻습니다.
다익스트라와 비슷해 보이기
힙을 사용하는 반복문은 다익스트라 알고리즘과 비슷하지만, 경로 거리가 아니라 원래 간선 가중치를 비교합니다. 이 패턴을 알아두면 코딩 시간을 절약할 수 있습니다. ⚡
빠른 확인
프림 알고리즘이 매 라운드마다 다음 간선을 선택하는 방식을 떠올려 보십시오.
복습
프림 알고리즘으로 MST를 만들었습니다. 어디서든 시작하고, 최소 힙을 사용해 가장 저렴한 경계 간선을 추가하며, 오래된 방문 항목은 건너뜁니다. 훌륭합니다! 🎉
자주 묻는 질문
“힙을 이용한 프림의 MST” 강의는 무료인가요?
네 — “힙을 이용한 프림의 MST” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“힙을 이용한 프림의 MST”에서 뭘 배우나요?
하나의 정점에서 트리를 확장합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“힙을 이용한 프림의 MST” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 경로 압축을 적용한 DSU
- 랭크에 따른 합치기와 구성 요소
- 크루스칼의 최소 신장 트리
- 힙을 이용한 프림의 MST