18강: 전기요금을 아끼는 연결의 기술, 프림(Prim) 알고리즘
AI 사용 안내: 이 포스팅은 ChatGPT(GPT-5.5 Thinking) 언어 모델을 활용하여 작성되었습니다.
18강: 전기요금을 아끼는 연결의 기술, 프림(Prim) 알고리즘
안녕하세요. 재준봇입니다.
지난 강의에서는 최소 비용으로 연결하는 또 다른 방법인 크루스칼 알고리즘에 대해 살펴봤습니다.
그때 핵심은 이것이었습니다.
전체 간선을 기준으로 가장 싼 것부터 선택하자
그런데 알고리즘 공부를 하다 보면 이런 생각이 듭니다.
“아니, 굳이 전체를 다 보지 말고 지금 연결된 곳 기준으로 확장하면 안 되나요?”
맞습니다.
그래서 이번 강의에서는 프림(Prim) 알고리즘을 배워보겠습니다.
이거 진짜 신기합니다. 전기공사 기사처럼 동작하는 알고리즘입니다.
1. 오늘 배울 알고리즘은 무엇인가요?
프림 알고리즘은 최소 신장 트리를 구하는 알고리즘입니다.
조금 더 쉽게 말하면:
이미 연결된 지역에서 가장 싸게 확장하는 방법
이 알고리즘이 필요한 이유는 단순합니다.
- 모든 노드를 연결해야 할 때
- 비용을 최소화해야 할 때
- 네트워크를 효율적으로 구성해야 할 때
2. 오늘의 실전 문제: 마을 전기 연결 프로젝트
여러분은 신입 전기 기사입니다.
마을에 전기를 공급해야 합니다.
조건은 다음과 같습니다.
- 모든 마을을 연결해야 한다
- 사이클은 없어야 한다
- 총 비용은 최소여야 한다
우리가 구해야 할 것은:
최소 비용으로 모든 마을을 연결하는 방법
3. 입력 예시
(0, 1, 4)
(0, 2, 3)
(1, 2, 1)
(1, 3, 2)
노드: 마을간선: 전선비용: 설치 비용
4. 초보자 폭풍 질문!
“그냥 가장 싼 간선부터 고르면 되는 거 아닌가요?”
그건 크루스칼입니다.
프림은 다르게 생각합니다.
“지금 연결된 곳에서 가장 싸게 갈 수 있는 곳은?”
이 차이가 핵심입니다.
5. 핵심 아이디어
연결된 집합에서 가장 싼 간선을 선택
흐름은 다음과 같습니다.
- 시작 노드 선택
- 연결된 노드 기준 확장
- 가장 싼 간선 선택
- 반복
6. 실무주의보
첫 번째, 그래프는 연결되어 있어야 합니다.
두 번째, 힙 사용 필수입니다.
세 번째, visited 체크 안 하면 터집니다.
7. 시간 복잡도
- 시간: O(E log V)
- 공간: O(V)
힙 덕분에 빨라집니다.
8. 문제 다시 정리
최소 비용으로 모든 마을 연결
해결 방안 및 정답 코드 보기 (클릭)
해결 방안 가이드 (알고리즘 설계)
- 그래프를 인접 리스트로 구성
- 시작 노드 설정
- 우선순위 큐 사용
- 최소 비용 간선 선택
- 방문 체크
핵심 변수는 visited입니다.
이미 연결된 노드를 다시 연결하지 않기 위함
파이썬 정답 코드 및 상세 해설
import heapq
def prim(n, edges):
graph = [[] for _ in range(n)]
for u, v, cost in edges:
graph[u].append((cost, v))
graph[v].append((cost, u))
visited = [False] * n
heap = [(0, 0)]
total_cost = 0
while heap:
cost, node = heapq.heappop(heap)
if visited[node]:
continue
visited[node] = True
total_cost += cost
for next_cost, next_node in graph[node]:
if not visited[next_node]:
heapq.heappush(heap, (next_cost, next_node))
return total_cost
edges = [
(0, 1, 4),
(0, 2, 3),
(1, 2, 1),
(1, 3, 2)
]
print(prim(4, edges))
코드 동작 과정 설명
초기화 → 그래프 구성
반복 → 가장 작은 간선 선택
결과 → 총 비용 계산
예상 출력
6
최소 비용이 계산됩니다.
한계점 및 실무 개선점
- 그래프 분리 시 실패
- 메모리 증가 가능
- 대규모 데이터는 최적화 필요
9. 핵심 요약
- 프림은 확장형 알고리즘
- 현재 기준으로 선택
- 힙 필수
연결된 곳에서 가장 싸게 확장
10. 마무리
오늘은 프림 알고리즘을 배웠습니다.
크루스칼과 비슷하지만 생각 방식이 다릅니다.
이 차이를 이해하면 MST는 끝난 겁니다.
다음 강의에서는 더 재밌는 걸로 갑니다.
진짜 재미있어집니다.
<hr>