Py) 프로그래머스 42861 섬 연결하기

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

코딩테스트 연습 - 섬 연결하기

 

# kruskal 알고리즘 - MST 사용, 최소의 비용으로 사이클을 형성하지 않음

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])  # kruskal1 - 오름차순 정렬
    # costs 내부 원소들을 기준으로 sorting 할건데 그 내부의 2번째 원소 기준으로

    candi = set([costs[0][0]])      # 주의!

    while len(candi) != n:          # kruskal2 - 사이클 형성하지 않으면서 연결
        for i in costs:
            if i[0] in candi and i[1] in candi:
                continue
            if i[0] in candi or i[1] in candi:
                candi.update([i[0], i[1]])      # 주의!!
                answer += i[2]
                break

    return answer

 

*피드백

set에 원소로 들어가는건데 계속 []를 안넣어서 not iterable이라는 오류가 계속 뜸

*

kruskal 알고리즘, union-find

예전에 정리해둔게 도움이 많이 됨

2019.11.19 - [Algorithm/Concept] - Union-Find(Disjoint-Set) 합집합 찾기

Union-Find(Disjoint-Set) 합집합 찾기