Q43. 어두운 길

문제참고

[이코테] 그래프 알고리즘 - 어두운 길 (tistory.com)

[이코테] 그래프 알고리즘 - 어두운 길

 

 

이건 문제 읽어보니까 그냥 최소신장트리 냄새가 술술나는데?

minimum spanning tree 써주세요~!!! 하고 소리치는거같다 ㅋㅋㅋㅋㅋ

마침 union find 구현해보고 하루이틀이 흘렀으니 복습할때가 됐는데 잘됐다 굳굳

 

######### input ##########

N, M = map(int, input().split())
edges = []
for _ in range(M):
    X, Y, Z = map(int, input().split())
    edges.append((Z,X,Y))
edges.sort()

###########################

##### union-find #####

parent = [i for i in range(N)]
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, x, y):
    p1 = find(parent, x)
    p2 = find(parent, y)

    parent[max(p1,p2)] = min(p1,p2)

######################

####### main #########
minimum = 0
total = 0
for cost, v1, v2 in edges:
    total += cost
    if find(parent, v1) != find(parent, v2):
        minimum += cost
        union(parent, v1, v2)

print(total - minimum)
######################