[Erin] Prim Algorithm

1922

힙 자료구조를 이용하면 좋다고 들었지만,,, 고집에 의해,,, 시간은 시간대로 태운 문제,,, 이다,,, ㅎㅎ,,,

Heap

힙은 자료구조 중에서도 완전 이진트리를 기반으로 하는 자료구조이다.

완전이진트리는 마지막 리프노드를 제외한 모든 노드들에서 자식이 꽉 채워진 이진트리를 의미한다.

힙은 최대힙과 최소힙으로 나뉘는데, (일반적으로 말하는 힙은 최대힙)

최대힙은 부모노드의 값이 어느 자식노드의 값보다도 크고

최소힙은 부모노드의 값이 어느 자식노드의 값보다도 작다.

이런 힙의 구조적 특성때문에 힙은 최댓값 혹은 최솟값을 빠르게 찾기 좋은 자료구조이다.

그리고 힙은 완전 이진트리이기 때문에 왼쪽부터 오른쪽으로 노드가 저장되므로 배열 구조를 이용하여 구현한다.

Prim Algorithm

프림 알고리즘은 힙 자료구조를 사용하는 그리디 알고리즘이다.

프림 알고리즘은 최소 비용 신장 트리(MST, Minimum Spanning Tree)와 같은 문제를 해결하기 적합한데,

최소 비용 신장 트리는 주어진 그래프에서 만들 수 있는 신장 트리 중 값이 가장 작은 신장 트리이며

따라서 도로나 네트워크를 최소비용으로 구축하는 등의 문제가 이에 해당한다.

아이디어

1. 시작점에서 출발하여 신장 트리를 단계적으로 확장

   (단, 여기서 어떤 것이 시작점이 되더라도 최종적인 비용은 같게 되므로 시작점은 아무거나 가능)

2. 신장 트리의 인접한 노드에서 최저 비용 간선으로 연결된 노드를 선택하여 신장 트리에 추가

3. 신장 트리가 n-1개의 최저 비용 간선을 가질 때까지 반복

구현하기

구현은 생각보다 간단했다.

초기화

초기화해야할 것이 두가지가 있는데,

먼저 graph는 간선들이 저장될 빈 리스트로 구성된 이중리스트이고,

visited는 비용을 체크하려는 노드가 이미 방문한 노드(연결된 노드)인지 체크하기 위한 리스트이다.

graph = [[] for _ in range(N + 1)]
visited = [False for _ in range(N + 1)]

a와 b를 잇는 edge의 비용이 c라고 할 때,

graph는 a번째 리스트에 (c, b) 형태로 넣어 저장하며

이때 비용과 같이 저장된 b는 다음에 탐색할 노드가 될 예정이다.

프림 알고리즘

프림 알고리즘에서 처음에 노드를 선택하는데(1번 노드로 하겠음), 이는 비용이 0이므로 (0, 1)을 추가하고 시작한다.

현재 노드가 탐색되었는지 visited를 체크하고 탐색되지 않았다면 값을 False에서 True로 변경해준다.

그리고 비용을 더해주면 한 노드에서 다른 노드로 가는 최저 비용이 더해진 것이 된다.

그리고 이렇게 최저 비용이 더해졌다면, graph에서 현재 노드에서 인접한 노드들의 정보를 다시 heap에 넣고 반복한다.

heap을 사용하지 않았을 때 이 부분을 구현하다가 때려치게 애를 먹게 되었는데

역시 괜히 패키지로 만들어둔게 아닌가보다.

def Prim():
    answer = 0
    queue = []
    heapq.heappush(queue, (0, 1))   # 아이디어 1에 해당

    while queue:
        cost, now = heapq.heappop(queue)
        if visited[now] == False:
            visited[now] = True
            answer += cost
            for next_cost, next_node in graph[now]:   # 아이디어 2에 해당
                heapq.heappush(queue, (next_cost, next_node))
    return answer

아이디어 3을 구현하려면 while문 대신 for문을 (N-1)회 돌도록 하면 된다.

Reference

• https://sexy-developer.tistory.com/58

• https://wookcode.tistory.com/173