알고리즘/프로그래머스(Programmers)

최소 신장 트리, C++ 최소 신장 트리, MST(Minimum Spanning Tree) 알고리즘은 두 가지 방식으로 풀 수 있다. 크루스칼 알고리즘과 프림 알고리즘이다. 크루스칼 알고리즘은 간선을 가중치가 작은 순서대로 오름차순으로 정렬을하고, 사이클을 형성하지 않는 방향으로 간선을 선택하며 트리를 구성한다. 정점이 많을 때 효과적인 알고리즘이다. 프림 알고리즘은 아무 정점을 시작 정점으로 설정한 뒤, 시작 정점의 인접 정점들 중에 가장 가중치가 작은 간선을 선택하며 정점을 잇는다. 하나의 정점을 잇게 되면, 현재까지 방문한 정점들의 인접 정점중에서 방문하지 않으면서 가장 작은 가중치를 가진 간선을 선택하는 알고리즘이다. 이렇게 되면 문제는 정점이 많아지게 된다면, 이전 방문했던 모든 정점들의 인접 ..