[프로그래머스/파이썬] 섬 연결하기

나의 풀이

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

def union(parent, x, y):
    x, y = find(parent, x), find(parent, y)
    if x > y:
        parent[x] = y
    else:
        parent[y] = x

def solution(n, costs):
    answer = 0
    parent = [i for i in range(n)]
    costs.sort(key=lambda edge: edge[2])

    for i in range(len(costs)):
        a, b, cost = costs[i]
        if find(parent, a) != find(parent, b):
            union(parent, a, b)
            answer += cost

    return answer

 

 

 

heapq를 사용한 풀이

import heapq as hq

def solution(n, costs):
    answer = 0
    from_to = list(list() for _ in range(n))
    visited = [False] * n
    priority = []

    for a, b, cost in costs:
        from_to[a].append((b, cost))
        from_to[b].append((a, cost))

    hq.heappush(priority, (0, 0))
    while False in visited:
        cost, start = hq.heappop(priority)
        if visited[start]: continue

        visited[start] = True
        answer += cost
        for end, cost in from_to[start]:
            if visited[end] : continue
            else:
                hq.heappush(priority, (cost, end))

    return answer