[백준] 1922. 네트워크 연결 - 파이썬

풀이.

최소 신장 트리 알고리즘인 크루스칼 알고리즘을 이용해서 풀면된다.

최소 비용을 구해야하는 문제이니 cost를 기준으로 graph를 정렬 시킨 후 

크루스칼 알고리즘을 이용하면 어렵지 않게 풀 수 있다.

최소 신장 트리 알고리즘이 가물가물해서 한번 풀어봤다.

 

소스코드.

<script src="https://gist.github.com/hanhyung6376/f6622fd34ba8c968bc12afce179c4d80.js"></script>

	import sys
	def union(a, b):
	a = find(a)
	b = find(b)
	if a < b:
	parent[b] = a
	else:
	parent[a] = b
	def find(target):
	if target == parent[target]:
	return target
	parent[target] = find(parent[target])
	return parent[target]
	def kruskal():
	cost = 0
	for u, v, w in graph:
	if find(u) != find(v):
	union(u, v)
	cost += w
	return cost
	input = sys.stdin.readline
	n = int(input())
	m = int(input())
	graph = []
	parent = [i for i in range(n+1)]
	for i in range(m):
	u, v, w = map(int, input().split())
	graph.append([u, v, w])
	graph.sort(key = lambda x: x[2])
	print(kruskal())

view raw 1922 - 네트워크 연결.py hosted with ❤ by GitHub