최소신장트리

🌳 최소 신장 트리 (MST)

1. 최소 신장 트리(MST)란 무엇일까?

가장 먼저, 용어부터 차근차근 분해해 봅시다.

• 그래프(Graph): 정점(Node)과 그를 잇는 간선(Edge)의 집합
• 신장 트리(Spanning Tree): 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프. 즉, 모든 정점을 연결하는 트리입니다.
• 최소 신장 트리(Minimum Spanning Tree): 신장 트리 중에서 간선들의 가중치 합이 최소인 트리.

💡 핵심 요약
주어진 그래프의 모든 정점들을 가장 적은 비용으로 연결하는 방법입니다.

---

2. MST의 핵심 조건 (Q&A 포함)

최소 신장 트리가 되기 위해서는 두 가지 핵심 조건을 반드시 만족해야 합니다.

Q1. 왜 사이클(Cycle)이 있으면 안 되나요?

결론부터 말하면, 사이클이 존재하면 '최소 비용'이라는 조건에 위배되기 때문입니다.

1. '트리'의 정의: '트리'라는 자료구조 자체가 '사이클이 없는 연결 그래프'로 정의됩니다. MST는 이름 그대로 '트리'이므로 이 정의를 따라야 합니다.
2. 비용의 모순: 만약 MST에 사이클이 있다고 가정해 봅시다. 이 사이클에서 가장 가중치가 높은 간선을 하나 제거해도 모든 정점은 여전히 연결된 상태를 유지합니다. 하지만 전체 비용은 더 줄어들게 되죠. 이는 '최소 비용'이라는 전제와 모순됩니다.

따라서 사이클은 비용을 줄일 수 있는 '낭비'를 의미하므로 MST에는 존재할 수 없습니다.

Q2. "가중치를 최소로, 사이클 없이, 간선이 N-1개가 될 때까지 연결"하는 것이 맞나요?

네, 완벽한 설명입니다! 👍

"N개의 정점을 가진 그래프에서 가중치가 낮은 간선부터 차례로 선택하되, 사이클을 형성하지 않는 간선만 골라 N-1개가 될 때까지 연결한다."

이 문장은 MST를 만드는 대표적인 알고리즘인 크루스칼(Kruskal) 알고리즘의 동작 방식을 정확하게 설명하고 있습니다.

• 가중치를 최소로: MST의 목표(Minimum)
• 사이클 없이: 트리의 조건(Tree)
• 간선 N-1개: 모든 정점을 연결하기 위한 조건(Spanning)

이 세 가지가 바로 MST를 구성하는 핵심 요소입니다.

---

3. 🐍 Python 구현 팁: 간선 리스트 정렬하기

크루스칼 알고리즘을 구현하려면 가장 먼저 모든 간선을 가중치 순으로 정렬해야 합니다. 이때 간선 정보가 (정점1, 정점2, 가중치) 형태의 튜플로 리스트에 담겨있는 경우가 많습니다.

이전에 질문 주셨던 "튜플 리스트를 세 번째 요소(가중치)로 정렬하는 법"이 바로 여기서 사용됩니다.

# (정점1, 정점2, 가중치) 형태의 간선 리스트
edges = [(0, 1, 10), (0, 2, 15), (1, 3, 5), (2, 3, 12)]

# 세 번째 요소(인덱스 2)인 가중치를 기준으로 오름차순 정렬
# lambda 함수를 key로 사용하면 매우 간결합니다.
edges.sort(key=lambda x: x[2])

print(edges)

실행 결과:

[(1, 3, 5), (0, 1, 10), (2, 3, 12), (0, 2, 15)]

이렇게 정렬된 리스트를 가지고 순서대로 간선을 확인하며 사이클 발생 여부를 체크하면 크루스칼 알고리즘을 구현할 수 있습니다.

---

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

def find(v):
    if parent[v] == v:
        return v

    parent[v] = find(parent[v])
    return parent[v]

def union(a, b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[a] = parent[b]


# V(정점의 개수), E(간선의 개수)
import sys

sys.setrecursionlimit(10 ** 6)
V, E = map(int, sys.stdin.readline().split())

edge_graph = []
result = 0

# 에지 그래프를 채우자
for i in range(E):
    A, B, C = map(int, sys.stdin.readline().split())
    edge_graph.append((A, B, C))

# 우선순위 큐를 이용해야하나? 아님 3번째 요소를 정렬시키는 방법이 있나?
# 1. sorted()
# 2. list.sort()

edge_graph.sort(key=lambda x:x[2])

# 부모 노드 리스트를 만들자.
parent = [i for i in range(V + 1)]

# edge_list를 가중치 낮은 것부터 높은 것까지 돌리면서 사이클을 형성하지 않으면 에지를 잇자.(union)
for edge in edge_graph:
    start = edge[0]
    end = edge[1]
    weight = edge[2]

    # 항상 부모 노드 값을 확인 할려면 find를 쓰기
    if find(start) == find(end):
        continue

    union(start, end)
    result += weight


print(result)