최소 비용 트리 구하기
-
프림 알고리즘Algorithm/Theory 2020. 3. 6. 17:13
- MST(Minimum Spanning Tree)를 만드는 방법 중 하나입니다. - 현재 트리를 기준으로 가장 최소인 점을 찾아나가는 방식입니다. - 사이클을 확인할 필요가 없습니다. (현재트리를 기준으로 하기 때문에 사이클이 생기지 않습니다.) 프림 알고리즘은 현재까지 생성된 트리를 기준으로 가장 최소 비용의 간선을 선택해서 트리를 확장시켜 나갑니다. 현재 트리를 기준으로 한다는 말 속에는 이미 방문한 점은 방문하지 않는다는 말이 포함되어 있습니다. 때문에 자연스럽게 사이클이 생기지 않습니다 :) 과정은 간단합니다. 1. 현재 트리를 기준으로 최소 비용으로 방문 가능한 점을 방문합니다. 2. 새로운 점을 기준으로 최소 간선의 목록을 업데이트 합니다. 직접 문제를 하나 풀어보면 쉽게 이해하실 수 있으실..