[프로그래머스/Level3] 섬 연결하기(Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42861

문제 접근

그리디를 이용하여 최소 비용인 간선부터 찾아내야겠다는 생각은 했다.

하지만, 모두 연결될 때까지 선택하는 조건을 알지 못하였고, 결국 크루스칼 알고리즘을 검색하여 문제를 해결했다.

첫번째 소스 코드는 크루스칼 알고리즘을 이해하고 내 방식대로 짜본 코드이다.
두번째 소스 코드는 사람들이 흔히 짜는 find_parent 재귀와 union_parent를 참고하여 짜본 코드이다.

소스 코드

from collections import deque

def solution(n, costs):
    if not costs:
        return 0
    answer = 0
    
    costs.sort(key = lambda x: x[2])
    q = deque(costs)
    parent = [i for i in range(n)]
    
    while q:
        n1, n2, cost = q.popleft()
        if n1 > n2:
            n1, n2 = n2, n1
        
        if parent[n1] != parent[n2]:
            answer += cost
            update_parent, target_parent = parent[n1], parent[n2] 
            if parent[n1] > parent[n2]:
                update_parent, target_parent = parent[n2], parent[n1]
                
            parent[n1] = update_parent
            parent[n2] = update_parent
            
            while parent.count(target_parent):
                parent[parent.index(target_parent)] = update_parent
                
    return answer

from collections import deque


def find_parent(parent, i):
    if parent[i] != i:
        parent[i] = find_parent(parent, parent[i])
        
    return parent[i]


def union_parent(parent, u, v):
    root_u = find_parent(parent, u)
    root_v = find_parent(parent, v)
    
    if root_u < root_v:
        parent[root_v] = root_u
    else:
        parent[root_u] = root_v
        

def solution(n, costs):
    if not costs:
        return 0
    answer = 0
    
    costs.sort(key = lambda x: x[2])
    q = deque(costs)
    edges = []
    parent = [i for i in range(n)]
    
    while len(edges) < n - 1:
        u, v, cost = q.popleft()
        
        if find_parent(parent, u) != find_parent(parent, v):
            answer += cost
            edges.append((u, v))
            union_parent(parent, u, v)
    
    print(edges)
    return answer