[프로그래머스] 섬 연결하기

문제

[프로그래머스] 섬 연결하기

유사 문제 : [백준] 최소 스패닝 트리

문제 풀이 개념

최소 신장 트리(MST), 크루스칼 알고리즘

코드

def solution(n, costs):
    answer = 0
    global parent
    parent = [i for i in range(n)] # 각자 부모를 자기 자신으로 초기화
    costs.sort(key = lambda x : x[2]) # cost 기준으로 오름차순 정렬
    
    for cost in costs:
        if find_parent(cost[0]) != find_parent(cost[1]): # 사이클이 생기지 않음
            answer += cost[2]
            union(cost[0], cost[1])
            
    return answer

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

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

• costs를 돌면서 두 노드의 부모 노드가 다를 때(사이클을 발생시키지 않을 때), union을 통해 두 노드를 이어준다.
• find_parent(node) : node의 부모를 찾는 함수
• union(a,b) : a와 b 노드를 연결 시킬 때, 두 노드의 부모를 찾아서 부모의 값이 작은 걸로 다른 노드의 부모를 바꿔준다.