[이코테] 그래프 이론_어두운 길 (python)

문제

나의 풀이

1. 성공 but 앞에 이론 복습 했기 때문에..

• 며칠전에 복습했는데도 자꾸 까먹는다ㅠ

def find_parendt(parent, x): # 부모 찾기
	if parent[x] != x:
        parent[x] = find_parendt(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b): # 합치기
    a = find_parendt(parent, a)
    b = find_parendt(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split())
parent = list(range(1, n + 1)) # 부모를 담을 list 초기화: 자기 자신은 자기로

edges = []
all = 0
result = 0

for _ in range(m):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b)) # 비용 순으로 정렬해야해서 cost가 맨 앞으로
edges.sort()

for cost, a, b in edges:
    all += cost
    # 부모가 달라? 합치자
    if find_parendt(parent, a) != find_parendt(parent, b): 
        union_parent(parent, a, b)
        result += cost
print(all - result) # 전체 비용 - 최소신장트리의 비용