prim
-
Programmers) Lv3 섬 연결하기Algorithm/Programmers 2020. 3. 6. 19:39
출처: https://programmers.co.kr/learn/courses/30/lessons/42861 분류: Lv3 , Greedy MST의 대표적인 문제입니다!!! Prim 알고리즘으로 해결해봤는데요. 자세한 설명은 이론 설명 그 자체일 듯 합니당 다음글을 참고해주세용 :) /** * 현재 노드에 연결되어 있는 노드만 확인할 것이기 때문에 * 간단하게 목적지와 비용만 저장하는 Edge 를 정의합니다. */ struct Edge { var destination: Int var cost: Int } func updateDist(_ tree: [Edge], dist: inout [Int?]) -> [Edge] { for edge in tree { if let d = dist[edge.destinati..
-
프림 알고리즘Algorithm/Theory 2020. 3. 6. 17:13
- MST(Minimum Spanning Tree)를 만드는 방법 중 하나입니다. - 현재 트리를 기준으로 가장 최소인 점을 찾아나가는 방식입니다. - 사이클을 확인할 필요가 없습니다. (현재트리를 기준으로 하기 때문에 사이클이 생기지 않습니다.) 프림 알고리즘은 현재까지 생성된 트리를 기준으로 가장 최소 비용의 간선을 선택해서 트리를 확장시켜 나갑니다. 현재 트리를 기준으로 한다는 말 속에는 이미 방문한 점은 방문하지 않는다는 말이 포함되어 있습니다. 때문에 자연스럽게 사이클이 생기지 않습니다 :) 과정은 간단합니다. 1. 현재 트리를 기준으로 최소 비용으로 방문 가능한 점을 방문합니다. 2. 새로운 점을 기준으로 최소 간선의 목록을 업데이트 합니다. 직접 문제를 하나 풀어보면 쉽게 이해하실 수 있으실..