[Python] 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861

---

크루스칼 알고리즘 문제

정점으로 가는 비용을 오름차순으로 정렬하고 

맨 처음에 있는 요소 0을 부모요소로써 route에 추가하고 시작한다

0이 이미 부모로 존재하므로 현재 노드가 route에 없다면 두번째 조건문이 작동한다 

set 객체인 route에 부모노드인 cost[0], 자식노드인 cost[1]을 넣어주고 answer에 비용을 더해준다

추가된 정점은 삭제하거나 [-1,-1,-1] 같은 문제상 무의미한 값으로 바꾼다

 

from collections import defaultdict
def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    route = set([costs[0][0]])
    while len(route) != n:
        for i,cost in enumerate(costs):
            if cost[0] in route and cost[1] in route:
                continue
            if cost[0] in route or cost[1] in route:
                route.update([cost[0], cost[1]])
                answer += cost[2]
                del costs[i]
                break
    return answer