문제 링크

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

문제 설명

• 에지가 주어짐
• 섬들을 모두 연결할 때의 최소 비용

풀이

• 비용으로 오름차순 정렬
• 모든 start, end, cost를 돌면서
• s, e가 한 집합에 속하면 continue
• 아니면 union

Union-find 구현

• Parent 리스트
  • 루트가 아닐 경우 부모 노드를 저장
  • 루트일 경우 (해당 집합의 노드 개수) x (-1) 을 저장
• Find
  • 루트일 경우
    • 자신의 인덱스 리턴
  • 루트가 아닐 경우
    • 부모 노드를 갱신하고 부모의 인덱스 리턴
• Union
  • 사이즈가 작은 집합을 큰 집합에 union
  • 사이즈가 작은 집합의 루트 노드의 부모를 갱신
  • 사이즈가 큰 집합의 노드 개수 갱신

코드

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    parent = [-1] * n
    for s, e, c in costs:
        r1 = get_root(parent, s)
        r2 = get_root(parent, e)
        if r1 == r2:
            continue
        union(parent, r1, r2)
        answer += c
    return answer


def union(parent, r1, r2):
    if abs(parent[r1]) < abs(parent[r2]):
        r1, r2 = r2, r1
    parent[r1] += parent[r2]
    parent[r2] = r1


def get_root(parent, curr):
    if parent[curr] < 0:
        return curr
    parent[curr] = get_root(parent, parent[curr])
    return parent[curr]

참고

https://ssungkang.tistory.com/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find