[이코테] 그래프 이론_도시 분할 계획 (python)

문제

나의 풀이

1. 최소 신장 트리 - 크루스칼 알고리즘으로 풀이

# 마을을 두개로 분리하되 각각 모든 집이 최소한의 비용으로 연결되어야 함.
# 즉, 두개의 신장트리를 구해야함.
# 크루스칼 알고리즘으로 최소 신장 트리를 구한 뒤 가장 비용이 큰 길을 삭제하자.

# 특정 집이 속한 집합을 찾기
def find_parent(parent, x):
	# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
	if parent[x] != x:
		parent[x] = find_parent(parent, parent[x])
	return parent[x]
    
# 두 집이 속한 집합을 합치기
def union_parent(parent, a, b):
	a = find_parent(parent, a)
	b = find_parent(parent, b)
	
	if a < b:
		parent[b] = a # 번호가 작은 노드가 부모가 됨
	else:
		parent[a] = b
        
n, m = map(int, input().split()) # 집(노드)의 개수 n, 길(간선)의 개수 m

parent = [0] * (n + 1) # 부모 테이블 초기화
edges = [] # 모든 길을 담을 list
result = 0 # 모든 길의 총 유지비용을 담을 변수
max_cost = 0 # 가장 유지비용이 큰 길을 0으로 초기화

# 자기 자신의 부모는 자기 자신으로 초기화
for i in range(1, n + 1):
	parent[i] = i
    
# 모든 길(간선)에 대한 정보 입력 받기
for _ in range(m):
	a, b, cost = map(int, input().split()) # a 집과 b 집을 연결하는 길의 유지비용 cost
	edges.append((cost, a, b))
    
# 길을 유지비용 순으로 정렬
edges.sort()

# 간선을 하나씩 확인하면서, 사이클이 발생하지 않는 경우 집합에 포함
for edge in edges:
	cost, a, b = edge
    
	if find_parent(parent, a) != find_parent(parent, b):
		union_parent(parent, a, b)
		result += cost # 하나씩 총 유지비용에 더해감
		max_cost = cost # 최소 신장 트리는 가장 마지막에 계산되는 간선이 가장 비용이 큰 간선임
        
# 총 유지비용 - 가장 큰 비용
print(result - max_cost)