[BOJ/백준] 1647 도시 분할 계획 파이썬

문제 링크 : https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

MST 문제이다. 나는 크루스칼로 풀이 했다.

 

문제는 마을을 두개로 분리하고 두부분의 가중치의 합이 최소가 되어야한다.

정점을 n이라 했을 때 n-2개의 간선은 고르면 된다.

 

MST 문제를 풀때 n-1개의 간선을 고르면 된다.

n-1개를 고르면 하나의 그래프가 탄생하고 사이클이 형성되지 않은 상태이다.

이때 간선을 하나 지우면 두개의 그래프가 나올 것이고 두개의 그래프 모두 가중치의 합이 최소가 될 것이다.

왜냐 크루스칼로 간선 선택 시 가중치가 작은 순으로 선택하기 때문이다.

 

from sys import stdin

input = stdin.readline

n,m = map(int, input().split())

edges = [tuple(map(int, input().split())) for _ in range(m)]
edges.sort(key=lambda x:x[2])
parent = [i for i in range(n+1)]

def solv():
    print(kruskal())
def kruskal():
    edge_count = 0
    cost = 0
    for a,b,c in edges:
        if not is_same_parent(a,b):
            union(a,b)
            cost += c
            edge_count += 1
            if edge_count == n-2:
                return cost
def find(target):
    global parent
    if parent[target] == target:
        return target
    parent[target] = find(parent[target])
    return parent[target]

def union(a,b):
    global parent
    a = find(a)
    b = find(b)

    if a != b:
        if a > b:
            parent[a] = b
        else:
            parent[b] = a

def is_same_parent(a,b):
    return find(a) == find(b)
solv()