[Python] 프로그래머스 선 연결하기 | 크루스칼 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

- 크루스칼 알고리즘을 이용하여 최소 스패닝 트리 찾는다.

- 간선 비용 기준으로 오름차순 정렬하여 순서대로 사이클이 발생하지 않으면 연결해 나간다

 

 

크루스칼 알고리즘 정리 글

2023.05.29 - [🧪Computer Science/알고리즘] - [알고리즘] 최소 스패닝 트리 알고리즘 | 크루스칼/프림 알고리즘

 

작성 코드

def solution(n, costs):
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        a, b = find(a), find(b)
        minP, maxP = min(a, b), max(a, b)
        parent[maxP] = minP

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

    costs.sort(key=lambda x: x[2])

    for a, b, w in costs:
        if find(a) != find(b):
            union(a, b)
            result += w
    return result

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚