[백준] 1647. 도시 분할 계획 - python

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

난이도: 골드 4

알고리즘: 최소 스패닝 트리(크루스칼)

풀이과정

문제에서 요구하는 사항은 도시를 둘로 나누고 최소 유지비용을 구하는 것.

여기서 서로 다른 도시의 집끼리는 이어질 필요가 없고, 같은 도시 내에서는 연결된 경로가 존재해야 한다.

최소 스패닝 트리를 이용하면 집끼리 모두 연결되면서 가중치가 최소인 간선들만을 선택할 수 있다.

이렇게 선택된 간선들 중 가장 가중치가 큰 간선을 빼면 도시가 두 부분으로 나뉘면서 최소 유지비용으로 도시를 두 개로 분할하는 경우를 구할 수 있다.

소스코드

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]


def union(a, b):
    global parent
    parent_a = find(a)
    parent_b = find(b)
    if parent_a < parent_b:
        parent[parent_b] = parent_a
    else:
        parent[parent_a] = parent_b


n, m = map(int, input().split())
roads = []
for _ in range(m):
    a, b, cost = map(int, input().split())
    roads.append((cost, a, b))

roads.sort()
parent = [i for i in range(n + 1)]
kruskal_result = []
for cost, a, b in roads:
    if len(kruskal_result) == n - 1:
        break
    if find(a) != find(b):
        union(a, b)
        kruskal_result.append(cost)
print(sum(kruskal_result) - max(kruskal_result))