MST2 [백준][트리] 1197 최소 스패닝 트리(크루스칼 알고리즘) 이 문제는 최소 스패닝 트리를 구현하는 방법중 크루스칼 알고리즘을 이용하여 구현하면 된다. 크루스칼 알고리즘은 그래프 사이 연결의 최소비용을 찾으면 된다. 간선을 비용순으로 정렬하고,가장작은 비용이 들어가는 간선을 사이클이 생기지 않는 순서대로 선택하면된다. 간선 사이의 사이클은 union, find 연산을 이용하여 처리한다. https://www.acmicpc.net/problem/1197 2017. 7. 6. [알고리즘] 최소비용 신장트리 - 프림알고리즘 최소비용 신장트리 구현알고리즘 중에서 프림알고리즘을 구현해 보았다. 프림알고리즘은 하나의 노드를 선택해서 다른노드로 가는 최소비용의 간선을 선택하고, 다음에는 선택한 노드중에서 나머지 노드로 가는 최소비용의 간선을 선택하여 최소비용 트리를 구현하는 것이다. 2017. 4. 18. 이전 1 다음