🌲 최소 신장 트리 (MST, Minimum Spanning Tree)

• 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것
• Spanning Tree 란?
  • 최소 연결 부분 그래프
  • 모든 정점들이 연결되어 있어야 하고, 사이클을 포함해서는 안된다.
  • K 개의 정점을 K-1 개로 연결한다.

🌱 Kruskal Algorithm

• 간선들을 중심으로 그리디 알고리즘을 통해 MST를 구하는 알고리즘

구현 방법

1. 그래프의 간선들을 가중치 기준 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
   • 가장 낮은 가중치 먼저 선택
   • 사이클을 형성하는 간선은 제외 - Union Find 알고리즘을 이용하여 사이클 형성 여부 확인
3. 해당 간선을 현재의 MST 집합에 추가한다.

코드 작성

arr = [0]*200

k = int(input())  # 정점 개수
n = int(input())  # 간선의 정보 개수
# [노드1, 노드2, 가중치] 리스트
lst = [list(input().split()) for _ in range(n)]

# 가중치 기준으로 정렬
lst.sort(key=lambda x:int(x[2]))

# find 연산
def findboss(member):
    if not arr[ord(member)]:
        return member
    ret = findboss(arr[ord(member)])
    return ret

# union 연산
def union(a, b):
    global total, cnt
    fa, fb = findboss(a), findboss(b)
    # 루트노드 같으면 사이클 존재하는 것이므로 리턴하기
    if fa == fb:
        return
    # 사이클 없으면 가중치 저장하고
    total += int(lst[i][2])
    cnt += 1  # 다리 개수 증가
    # union 하기 
    arr[ord(fb)] = fa

total = 0  # 최소 비용
cnt = 0  # 다리 개수
for i in range(n):
    if cnt == k-1:  # k개의 정점을 k-1개로 연결하면 최소비용 출력하고 break
        print(total)
        break
    union(lst[i][0], lst[i][1])

⭐️ 문제 추천

[BOJ] - 1197. 최소 스패닝 트리