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

📝 문제

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

🎯 풀이

Kruskal 알고리즘으로 풀어내면 쉬운 문제.
Kruskal 알고리즘은 Union-find + Sorting 이 더해진 알고리즘이다.

Union-find 없이 최저비용 연결만 진행하면 Cycle이 발생할 수 있다.
이 때문에 Union-find가 적용되면 좋은데,
최저비용(오름차순 정렬) + Union-find = Kruskal
결국 Kruskal 이라는 말이다.

Kruskal 알고리즘에 대한 자세한 설명은 안경잡이개발자님 블로그에 잘 정리되어 있다.

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2]) # 비용기준 오름차순 정렬
    union = [i for i in range(n)]  # union-find 리스트 선언.
    
    for s, d, cost in costs:
        if union[s] != union[d]:   # union-find 값이 같으면 이미 연결된 상태.
            dest = union[d]
            for i in range(n):     # 도착섬과 같은 값들을 모두 시작섬으로 변경
                if union[i] == dest:
                    union[i] = union[s]
            answer += cost         # 최저 비용 더하기.
        
            check_point = 0        # 모든 섬이 연결되었나 판별.
            for c in range(n-1):
                if union[c] != union[c+1]:
                    check_point = 1
            if check_point == 0:
                break
                
    return answer

프로그래머스 파이썬 문제풀이는 정말 오랜만에 하는 것 같다.
LEVEL 3 부터 급격히 높아진 난이도에 많이 주저했었는데,
이제 조금씩 풀어내는걸 보면 실력이 늘긴 느나보다. 😆