백준 : 1197 최소 스패닝 트리

Kruskal 은 “ 간선 중심 “ 알고리즘이다

• 가장 작은 가중치의 간선부터 하나씩 선택하며 사이클이 생기지 않도록 주의해서 신장 트리를 만들어간다
• 이때 가장 중요한 건 간선 정렬과 Union-Find 자료구조를 통한 사이클 판별이다

Prim 은 “ 정점 중싱 “ 알고리즘이다

• 하나의 정점에서 시작해서, 아직 방문하지 않은 정점 중에서 가장 가까운 정점으로 확장해나간다
• 이때는 Min-Heap (우선순위 큐)을 활용해서 매번 가장 짧은 간선을 빠르게 선택한다

두 알고리즘 모두 MST를 구하지만, 그 접근 방식이 다르기 떄문에 구현을 해보면서 내가 어떤 자료구조를 다루고 있는지, 문제가 어떤 그래프 구조를 가졌는지에 따라 알고리즘 선택이 달라질 수 있음을 알 수 있었다.

결론 도출

1. 결과는 같더라도, 과정은 전혀 다르다
2. → 같은 MST 문제라고 해도, 사용하는 알고리즘과 자료구조는 다를 수 있다.
3. 그래프 구조에 따라 선택이 달라진다
4. → 간선이 많은 Dense 그래프라면 Prim, 간선이 적은 Sparse 그래프라면 Kruskal이 유리하다.
5. 자료구조와 연결 방식이 진짜 중요하다
6. → Kruskal의 Union-Find, Prim의 힙 구조를 직접 다뤄보면서 내부 흐름을 이해하게 되었다.

최종 코드

Kruskal 방식으로 풀이

import sys
sys.setrecursionlimit(10**6)

# a가 루트가 아니라면 재귀적으로 루트를 찾아서 parent를 루트로 갱신하고, 루트를 반환
def find(a):
    if a!= parent[a]:
        parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    rootA = find(a)             #각각 루트를 찾음
    rootB = find(b)
    if rootA != rootB :         #루트가 다른 경우 -> 다른 집합
        parent[rootB] = rootA   #한쪽 루트를 다른 쪽에 붙인다 (하나의 집합으로 합친다)

input = sys.stdin.readline
V, E = map(int, input().split())
tree = []
for _ in range(E):
    tree.append(list(map(int, input().split())))

tree.sort(key=lambda x: x[2])   #간선들을 가중치 기준으로 오름차순 정렬
parent = list(range(V+1))       #Union-Find용 부모 배열 초기화 (자기 자신이 부모)

ans = 0
for a, b, c in tree:
    if find(a) != find(b):      #a와 b가 같은 집합에 속하지 않는다면 (사이클 아님)
        union(a, b)             #두 정점을 연결 (집합 병합)
        ans += c                #가중치를 누적 증가
        
print(ans)

Prim을 이용한 풀이

import sys
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**6)

def prim(graph, start, V):
    visited = [False]*(V+1)     #정점 번호가 1부터 시작으로 V+1 크기로 초기화
    min_heap = [(0, start)]     #(가중치, 정점)
    total_weight = 0            #MST의 총 가중치 누적
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)     #최소 가중치 간선 꺼내기
        
        if visited[u]:          #MST 포함된 정점은 무시
            continue
        visited[u] = True       #MST에 현재 정점 포함
        total_weight += weight  #해당 간선 가중치 누적
        
        #현재 정점과 연결된 인접 정점 확인
        for (v, cost) in graph[u]:
            if not visited[v]:          #아직 MST에 포함되지 않은 정점만
                heapq.heappush(min_heap, (cost, v))     #다음 후보 간선 추가
                
    return total_weight                 #MST 완성 -> 총 가중치 변환
    
input = sys.stdin.readline
V, E = map(int, input().split())        

graph = defaultdict(list)
for _ in range(E):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))         #a -> b 간선 추가
    graph[b].append((a, c))         #b -> a 간선 추가 (무방향 그래프라서 양방향)

#프림 알고리즘 실행 (정점 1에서 시작)
print(prim(graph, start=1, V=V))

 

크루스칼은 간선 리스트 (edge list)로 데이터를 받아서 풀이 (리스트 이용)

프림은 인접 리스트로 데이터를 받아서 풀이 (dictionary 이용)