백준 #1647 도시분할계획 : 크루스칼 알고리즘과 유니온파인드

https://www.acmicpc.net/problem/1647

최소 스패닝 트리(MST)를 구하는 알고리즘에는 크게 두가지가 있음.

크루스칼 알고리즘​ - 간선들을 가중치에 따라 오름차순 정렬을 해야함. 간선 개수가 적으면 유리. 가중치가 적은 순서대로 트리에 추가하되 사이클이 생기는 경우는 제외

프림 알고리즘 - 아무 정점이나 하나 고르고 연결된 모든 간선을 집합에 추가한다. 가중치가 가장 작은 간선을 선택하고 그 간선을 따라 도착한 정점의 모든 간선도 집합에 추가한다. 한번 들렀던 정점은 다시 들르지 않는다.

​

<<크루스칼, 유니온파인드를 활용한 기본 문제>>

https://blog.naver.com/jennifer0606/222417769159

백준 #1922 네트워크 연결 : 최소신장트리(MST)

 

나는 크루스칼 알고리즘을 선택했고, 크루스칼의 속도를 높이는 몇가지 방법이 있다.

1. N-1개의 간선이 트리에 추가되면 즉시 종료한다.

2. 사이클이 생기는 경우를 체크하는데는 Union Find 자료구조를 활용한다.

​

최소 신장 트리를 구하고 가장 가중치가 높은 간선 하나만 제거하면 위 문제를 해결할 수 있다.