[Level3] 섬 연결하기

🛠 문제

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

👩🏻‍💻 해결 방법

그래프(트리) + 최소의 비용을 읽고 크루스칼 알고리즘을 떠올려 문제를 해결했다

소스 코드

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x:x[2])
    parent = [0] * n
    for i in range(n):
        parent[i] = i
    
    for cost in costs:
        a, b, c = cost
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += c
            
    return answer

💡 다른 사람의 풀이

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x:x[2])
    routes = set([costs[0][0]])
    
    while len(routes) != n:
        for i, cost in enumerate(costs):
            if cost[0] in routes and cost[1] in routes:
                continue
            elif cost[0] in routes or cost[1] in routes:
                routes.update([cost[0], cost[1]])
                answer += cost[2]
                costs[i] = [-1, -1, -1]
                break
    return answer