[Programmers | Level 3] 섬 연결하기 (Python)

 

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


def union(a, b):
    global parent
    x = find(a)
    y = find(b)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


parent = []


def solution(n, costs):
    global parent
    parent = [0] * n
    for i in range(n):
        parent[i] = i

    t = sorted(costs, key=lambda x: x[-1])
    result = 0
    for i in t:
        if find(i[0]) != find(i[1]):
            union(i[0], i[1])
            result += i[2]

    return result

크루스칼 알고리즘을 이용하여 MST를 찾는 방식으로 해결하였다.

union find와 세트이므로 기본 구조는 술술 나오도록 암기하자! 그래야 실전에서 빠르게 풀 수 있다.

크루스칼의 핵심 : 간선 비용 오름차순으로 정렬한 뒤 사이클이 생기지 않도록 반복해서 union