[트리] 1197번 : 최소 스패닝 트리

- 출제 문제 

 해당 문제는 최소 스패닝 트리(MST)를 직접 구현해 볼 수 있는 문제이다. 최소 스패닝 트리란 정점이 있을 때 연결하는 부분의 가중치의 합이 최소인 트리를 말한다.

 

만약, A에서 B 정점으로 이동 할 때 거리가 5 혹은 10이 있다면 5를 선택하여 가중치가 최소가 될 수 있도록 선택하는 것이다.

 

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

---

- 접근 방법

우선 MST를 구성하는 방법은 크루스칼 알고리즘, 프림 알고리즘 2종류가 있다. 

 

크루스칼 알고리즘의 경우 가중치가 최소인 정점 간 간선을 그어 놓고, 간선이 만들어진 정점간 연결하는 방법이고,

 

프림 알고리즘의 경우 최소 가중치를 가지고 있는 정점을 선택해 정점을 간선으로 이어가며 최소 가중치 합을 구하는 트리이다.

 

보통 크루스칼은 간선의 개수가 적을 때, 프림의 경우 정점의 개수가 많을 때 사용하는 알고리즘이라고 한다.

---

- 완성 코드

[크루스칼 알고리즘]

import sys
input = sys.stdin.readline
 
V, E = map(int, input().split())
Vroot = [i for i in range(V+1)] # 부모 루트 초기 선언(자기 자신)
Elist = []


print(Elist)
Elist.sort(key=lambda x: x[2])
print(Elist)
def find(x):
    if x != Vroot[x]:
        Vroot[x] = find(Vroot[x]) # 최소 비용을 갖는 부모 루트와 연결
    return Vroot[x]
 
answer = 0

# 서로소 집합으로 이루어져 있는 부모끼리 연결
for s, e, w in Elist:
    sRoot = find(s)
    eRoot = find(e)
    if sRoot != eRoot:
        if sRoot > eRoot:
            Vroot[sRoot] = eRoot 
        else:
            Vroot[eRoot] = sRoot
        answer += w
 
print(answer)

 

[프림 알고리즘]

import sys
import heapq
input = sys.stdin.readline

v, e = map(int, input().split())
g = [[] for _ in range(v+1)]

# 양방향 연결
for _ in range(e):
    a, b, w = map(int, input().split()) 
    g[a].append((w, b))
    g[b].append((w, a))

q = g[1]
visited = [True,True] + [False]*(v-1)
heapq.heapify(q)
answer = 0
while q:
    w, dest = heapq.heappop(q)
    if not visited[dest]: # 아직 방문 전이라면
        visited[dest] = True
        answer += w
        for e in g[dest]: 
            if not visited[e[1]]:
                heapq.heappush(q,e)
print(answer)