[알고리즘/파이썬] 프로그래머스 - 섬 연결하기

문제

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

프로그래머스

 

풀이

가장 적은 비용의 간선부터 차례대로 사이클이 발생하지 않도록 연결해주면

최소비용신장트리를 구할 수 있다. (크루스칼 알고리즘)

 

 

코드

def solution(n, costs):
    answer = 0
    # 비용이 가장 적은 간선부터 정렬
    costs.sort(key = lambda x: x[2]) 
    # 처음 시작 노드 넣고 시작
    link = set([costs[0][0]])

    # Kruskal 알고리즘으로 최소 비용 구하기
    while len(link) != n:
        for v in costs:
        	# 사이클 생성 방지
            if v[0] in link and v[1] in link:
                continue
            if v[0] in link or v[1] in link:
            	# set의 update는 중복을 자동으로 없애준다
                link.update([v[0], v[1]])
                answer += v[2]
                break