[프로그래머스/42861/level3/고득점kit] 섬 연결하기 - 최소신장트리, 크루스칼 Kruskal 알고리즘

 

Kruskal 알고리즘

• 최소 신장 트리 찾는 대표적 그리디 알고리즘
• 최소한의 비용으로 구성되는 신장 트리 찾을 때 사용
• 비용이 적은 a, b 노드 사이의 간선을 하나씩 택하면서 두 노드가 둘다 집합에 이미 포함되어있으면 사이클이 생기니 건너뛰고, 둘중 하나라도 포함되지 않으면 UNION연산으로 집합에 합해준다.
• 방식
  1. 간선 테이터를 비용에 따라 오름차순으로 정렬한다.
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
     1. 사이클 발생하지 않는 경우에만 최소 신장 트리에 포함시킴
  3. 모든 간선에 대해 2번과정 반복
     1. 선택하느 간선개수는 (전체노드개수 - 1) 개

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

# 노드개수, 간선 개수 입력
v, e = map(int, input().split())

# 부모 테이블 초기화
parent = [0] * (v + 1)

edges = [] #모든 간선
resuslt = 0 #최종비용

# 부모를 자기자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

#모든 간선 정보 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

#간선 cost비용 순으로 정렬
    edges.sort()

#간선 하나씩 확인하며 - 사이클 발생하지 않는 경우에만 집합에 포함시킴
    for edge in edges:
        cost, a, b = edge
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            result += cost

 

문제

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

내 풀이 → 크루스칼 알고리즘 자체가 풀이 끝! 추가적인 요소는 없었다

#kruskal 알고리즘
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):
    '''
    [섬1, 섬2, 비용]
    '''
    parent = [i for i in range(n + 1)] #자기자신으로 초기화
    costs.sort(key = lambda x: x[2]) #비용순 정렬
    
    answer = 0
    for a, b, cost in costs:
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += cost
    
    return answer