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

[Gold IV]

 

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

1647번: 도시 분할 계획

 

풀이

문제를 딱 보고서 생각한 것

-> Minimum Spanning Tree구나.

MST를 구현하고 나서, 남은 edge들 중 가장 value가 높은 것을 제거하면 될 것 같다.

 

line 13의 = 를 ==로 오타내서 찾는데 시간 좀 씀...ㅎ

아무튼 clear.

from collections import deque
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
edges = sorted(edges, key=lambda x: x[2])

dic = {i: i for i in range(1, N+1)}
result = []  # save costs for edges(result)


def find(x):  # Find(Union-Find), with optimization
    if dic[x] == x:
        return x
    dic[x] = find(dic[x])
    return dic[x]


def union(x, y):  # Union(Union-Find), connect to smaller one.
    rx = find(x)
    ry = find(y)
    if rx < ry:
        dic[ry] = rx
    else:
        dic[rx] = ry


for edge in edges:
    if len(result) == N-1:
        break

    a, b, c = edge
    # cycle 생성이 되지 않는다면,
    if find(a) != find(b):
        union(a, b)
        result.append(c)

print(sum(result) - max(result))