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

1일 1PS 70일차!

📚 문제

---

골드 4 최소 스패닝 트리

💡 풀이 과정

---

• 최소 스패닝 트리는 Kruskal 알고리즘에 따랐다.
• 크루스칼 알고리즘이란?
  • 그래프 내 모든 정점을 가장 적은 비용으로 연결하기 위해 사용된다.
  • 즉, 모든 정점을 포함하고 사이클이 없는 형태의 그래프이다.
  • 가중치를 기준으로 간선을 오름차순 정렬 후 하나씩 확인하면서 해당 간선으로 사이클이 만들어지지 않는다면 (= 해당 간선이 새로운 정점 연결이 가능하다면) 간선을 추가한다.
  • 그리고 최소 비용으로 연결되기 위해서는 간선의 개수는 당연히 (정점의 개수 - 1) 개 이다. 그 이상은 무조건 사이클이 생겨 불필요한 비용이 발생한다.
• 그렇다면 사이클이 발생했는 지를 적은 비용으로 확인하는 것이 문제이다.
• 이는 Union-Find 를 사용할 수 있다.
  • 두 정점의 parent 가 동일하다면 같은 그룹 (이미 연결되어있는 정점) 으로 파악할 수 있으며 여기에 간선이 하나 더 생기는 것은 사이클이 생기는 것을 의미한다.
  • 서로 다른 그룹이거나 한 정점이 어느 누구와도 연결되어있지 않으면 간선을 추가해 연결해주어야한다.

📌포인트

---

💻 코드

---

import sys


class UnionFind():
    def __init__(self, N):
        self.data = [i for i in range(N + 1)]

    def find(self, N):
        if N == self.data[N]:
            return N
        self.data[N] = self.find(self.data[N])
        return self.data[N]

    def union(self, N, M):
        self.data[self.find(M)] = self.find(N)


input = sys.stdin.readline

V, E = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(E)]
uf = UnionFind(V)
weight = 0
cnt = 0

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

for v1, v2, w in edges:
    if cnt == V - 1:
        break
    if uf.find(v1) == uf.find(v2):
        continue

    weight += w
    cnt += 1
    uf.union(v1, v2)

print(weight)