BaekJoon1647_도시 분할 계획

문제

풀이

이 문제는 크루스칼 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다.
1. union-find 함수를 구현하여 지역들과 각 지역들을 연결한 간선 그리고 각 간선들의 크기를 저장한다.
2. 그 후 각 간선들의 크기를 오름차순으로 정렬한다.
3. 크루스칼 알고리즘으로 최소신장트리를 찾은 후 가장 큰 간선을 제거하면 된다.

풀이코드

v,e = map(int,input().split())

def find_parent(parent, a):
    if parent[a] != a:
        parent[a] = find_parent(parent, parent[a])
    return parent[a]

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
        
parent = [0] * (v+1)

edges = []
money = 0

for i in range(1, v+1):
    parent[i] = i
    
for _ in range(e):
    edges.append(tuple(map(int,input().split())))
    
edges.sort(key=lambda x: x[2])
temp =0
for edge in edges:
    a,b,cost = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        money += cost
        temp = cost
print(money - temp)