[TIL]Day 138

크루스칼(kruskal) 알고리즘이란 탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

크루스칼 알고리즘 동작
1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
3. 해당 간선을 현재의 최소비용신장트리 집합에 추가한다.

어떻게 사이클을 감지할 것인가

• 분리집합을 활용하여 해결한다.
• 각 정점들을 각가의 집합안에 입력하고, 간선으로 연결되어 있는 정점들에 대해서는 합집합을 수행한다.
• 이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 된다.

예를들어 A-D를 연결한다고 했을 때,

왼쪽은 A와 D가 별개의 집합으로 구성되어 있기 때문에 사이클이 형성되지 않지만, 오른쪽은 같은 집합에 속해있기 때문에 사이클이 형성됨.

파이썬 구현
https://it-garden.tistory.com/411

관련문제

• 프로그래머스 섬 연결하기

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x : x[2])
    routes = set([costs[0][0]])
    while len(routes) < n:
        for i, cost in enumerate(costs):
            if cost[0] in routes and cost[1] in routes:
                continue
            if cost[0] in routes or cost[1] in routes:
                routes.update([cost[0],cost[1]])
                answer += cost[2]
                costs[i] = [-1,-1,-1]
                break
    return answer