최소 신장(스패닝) 트리 - 크루스 칼 알고리즘!!

	# 최소 신장 트리 - 크루스 칼 알고리즘.
	import sys
	def find_parent(x):
	if parent[x] != x:
	parent[x] = find_parent(parent[x])
	return parent[x]
	def union_parent(x, y):
	x = find_parent(x)
	y = find_parent(y)
	if x < y:
	parent[y] = x
	else:
	parent[x] = y
	n = int(input())
	m = int(input())
	parent = [0]*(n+1)
	for i in range(1, n+1):
	parent[i] = i
	graph = []
	for i in range(1, m+1):
	a, b, c = map(int, sys.stdin.readline().split())
	graph.append((c, a, b)) # 리스트로 했을 때 보다 튜플로 했을 때 시간이 훨씬 적게 걸림. - 튜플이 메모리 효율성이 뛰어남.
	graph.sort() # 간선을 비용 순으로 정렬
	res = 0
	for i in graph:
	cost, a, b = i
	# 사이클이 발생하지 않는 경우에만 집합에 포함
	if find_parent(a) != find_parent(b):
	union_parent(a, b)
	res += cost
	else:
	continue
	print(res)

view raw 백준 1922번 네트워크 - 최소 신장 트리 - 크루스 칼 알고리즘 hosted with ❤ by GitHub