크루스칼 알고리즘

프로그래머스 LV3 레벨을 풀던중

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

프로그래머스

이 문제를 푸는데 당연히 난 다익스트라를 사용하여 푸려고 했다.

def solution(n, costs):

    costs = sorted(costs, key=lambda x:(x[2]))
    print(len(costs))

    dist =[1] + [0] * (n-1)
    graph = [ [] for _ in range(n)]
    for ( x, y, z ) in costs:
        graph[x].append((y, z))
        graph[y].append((x, z))
    # graph = [()] 이차원 리스트에서 각 리스트 가는 방향과 값.
    print(graph)
    q = deque([0])
    # print(graph,q,dist,sep="\n")
    res = 0
    while q:
        l = len(q)
        for i in range(l): # (0,1)
            now = q.popleft()
            for next_node, w  in graph[now]:
                if dist[next_node] == 0:
                    dist[next_node] = 1
                    q.append(next_node)
                    res += w
    return res

하지만 이렇게 하면 테스트코드 1개만 맞고 다 틀린다. 이유는 가장 적은 값을 가져오는게 아니기 때문이다

 

그래서 질문하기를 보니 다들 크루스칼 알고리즘과, 스칼 알고리즘을 사용하길래 크루스칼 알고리즘에 대해 알아보도록 하겠다.

 

크루스칼알고리즘

'가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘'

즉 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있다. 여러 노드와 여러 간선이 있을때 비용을 최소한으로 하려고 할때 사용되는 알고리즘이다. 섬연결하기 문제를 보자.

 

섬 연결하기 문제

노드는 4개이고, 간선의 갯수는 5개이다.

크루스칼 알고리즘의 핵심 개념은 간선을 거리가 짧은 순서대로 그래프에 포함시키는것이다. 그렇다는것은 일단 모든 노드를 최대한 적은 비용으로 연결시키면 되기 때문에 간선 정보를 오름차순으로 정렬한 후 차근차근 포함시키면된다.

(0.1) 1 (1.3) 1 (0,2)2 (1,2)5 (2,3)8

 

이렇게 모든 간선정보를 저장하면 총 5개이다. 3번 노드에 정보가 없는것은, 이미 다른 노드들의 간선정보에 모두 포함이 되어있어서 이다.

이제 다음 알고리즘에 맞게 그래프를 수행하면 "최소 비용 신장 트리" 가 만들어진다.

• 정렬된 순서에 맞게 그래프에 포함시키기
• 포함시키기 전에 사이클 테이블 확인
• 사이클 형성하는 경우 간선 포함 x

사이클이라는 것을 그래프가 서로 연결된 것을 말한다. 위에 그림에서 예를들면 0,1,2번 노드가 삼각형으로 사이클이 형성된것이다.

사이클의 발생하는지 여부는 Union-Find 를 사용해야하는데, 필자는 아직 몰라 구글링으로 알아본결과 간단히 합집합을 구하는것 같다. 다음에 제대로 알아보도록 하겠다.

 

(0.1) 1 (1.3) 1 (0,2)2 여기까지 진행하면 위에 그래프에서 초록색 선들이 연결된것이다. 근데 여기서 (1,2) 을 연결하면 1에 부모와 2에 부모인 0 과 연결되면서 사이클이 형성된다. 사이클이 형성되면 안 되기 때문에 지나치면 되는것이다. 그리고 다음에 (2,3)8 은 2와 3이 이미 연결되어 있으므로 무시하고 넘어가면 된다. 구현은 다시 풀고 섬 연결하기 문제에 남겨 두었다.

 

빅오

간선을 정렬하는 시간: O(E log E) (E는 간선의 수) 

유니온-파인드(Union-Find) 연산 시간: O(E α(V)) (α는 아커만 함수의 역함수로서 매우 느리게 증가)

 

https://windy7271.tistory.com/entry/PythonLV3-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0

(Python/LV3) 섬 연결하기