[크루스칼] 백준 1647번 '도시 분할 계획' (Python)

<문제 링크>

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

---

<문제 풀이>

1. 모든 노드를 포함하면서 사이클이 존재하지 않고, 최소비용으로 신장트리를 만들어야 하므로 크루스칼 알고리즘 적용

2. 비용순으로 간선 정렬

3. 사이클이 발생하지 않는 경우에만 집합 합치기

4. 최소 신장트리를 구성하는 간선 중에서 가장 비용이 큰 간선 제거

 

<코드>

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
        
v,e = map(int,input().split())
parent = [0] * (v+1)

edges = []
result = 0

for i in range(1,v+1):
	parent[i] = i
    
for _ in range(e):
	a,b,cost = map(int,input().split())
    edges.append((cost,a,b))
    
edges.sort()
last = 0

for edge in edges:
	cost,a,b = edge
    if find_parent(parent,a)!=find_parent(parent,b):
    	union_parent(parent,a,b)
        result += cost
        last = cost
        
print(result-last)

 

<고쳐야 할 점>

• 크루스칼 알고리즘 이해
• 신장 트리 이해
• 해당 문제 이해
• 복습 알고리즘