(Python) 프로그래머스 - 섬 연결하기

19 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

import heapq


def solution(n, costs):
    answer = 0

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

    q = []
    for x, y, cost in costs:
        heapq.heappush(q, (cost, x, y))

    while q:
        cost, x, y = heapq.heappop(q)

        if find_parent(parent, x) != find_parent(parent, y):
            answer += cost
            union(parent, x, y)

    return answer


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


def union(parent, x, y):
    x_parent = find_parent(parent, x)
    y_parent = find_parent(parent, y)

    if x_parent < y_parent:
        parent[y_parent] = x_parent
    else:
        parent[x_parent] = y_parent

find, union을 사용하는 무난한 최소신장트리 문제다.