[ Lv 3 ] 섬 연결하기

풀이 과정

---

1. 최소 비용 신장 트리 문제라고 볼 수 있으므로 Kruskal 알고리즘 사용

2. Cycle을 판단하기 위해 Union-find 알고리즘 사용

3. Kruskal 알고리즘을 사용하여 가중치가 최소인 간선부터 골라가면서 사이클을 형성하는지 체크하고, 사이클을 형성하지 않는다면 해당 간선 사용

4. 가중치가 최소인 간선을 고르기 위해 최소 히프 사용

---

import heapq

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])

    return parent[a]

def union(parent, a, b):
    t1 = find(parent, a)
    t2 = find(parent, b)
    if t1 != t2:
        parent[t1] = t2

def solution(n, costs):
    answer = 0
    heap = []
    for src, dest, cost in costs:
        heapq.heappush(heap, [cost, src, dest])

    selected_edges = 0
    parent = [i for i in range(n)]

    while heap:
        cost, src, dest = heapq.heappop(heap)
        t1 = find(parent, src)
        t2 = find(parent, dest)
        if t1 != t2:
            union(parent, src, dest)
            answer += cost
            selected_edges += 1
            if selected_edges == n-1:
                break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges