프로그래머스 : 섬 연결하기

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

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

 

해결 방법 : 그리디 Kruskal

• 최소 비용 신장 트리 문제이다.
• 그리디하게, 사이클을 만들지 않으면서 가장 작은 cost 간선을 추가
  • 간선 개수가 n-1이면 종료
  • 사이클 검사는 추가하려는 두 노드가 같은 그룹에 있는지 판단하면 된다.

def solution(n, costs):
    answer, lines = 0, 0 
    costs.sort(key=lambda x:x[2]) # cost 오름차순 정렬
    link = [i for i in range(n)] # 그룹 표시
    
    for f, t, c in costs:
        if link[f] != link[t]: # f와 t가 다른 그룹에 있을 경우
            temp = link[t] 
            for i, l in enumerate(link): # 같은 그룹으로 동기화
                if l == temp: link[i] = link[f]
                    
            answer += c
            lines += 1
        
        if lines == n - 1: break # 전체 라인이 n-1개이면 최소신장트리
        
    return answer