Union-Find, 최소신장 트리 (MST, Minimum Spanning Tree)
최소신장트리는 그래프에서 일부 간선을 선택해서 만든 트리이다. 이때 간선의 개수는 노드의 개수가 n개라고 했을 때 n-1개가 된다. 간선을 선택하는 방법은 greedy 한 방법으로 가장 최소의 비용이 드는 간선을 선택하고 이미 선택이 돼 있는 2개의 노드를 선택하지 않는 조건을 지켜가며 트리를 구성하게 된다.
참고 링크: https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
관련 예제
백준: 1922 네트워크 연결 https://www.acmicpc.net/problem/1922
1922번: 네트워크 연결
이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.
www.acmicpc.net
소스코드
백준: 3830 교수님은 기다리지 않는다 https://www.acmicpc.net/problem/3830
3830번: 교수님은 기다리지 않는다
문제 상근이는 매일 아침 실험실로 출근해서 샘플의 무게를 재는 일을 하고 있다. 상근이는 두 샘플을 고른 뒤, 저울을 이용해서 무게의 차이를 잰다. 교수님의 마음에 들기 위해서 매일 아침부터 무게를 재고 있지만, 가끔 교수님이 실험실에 들어와서 상근이에게 어떤 두 샘플의 무게의 차이를 물어보기도 한다. 이때, 상근이는 지금까지 잰 결과를 바탕으로 대답을 할 수도 있고, 못 할 수도 있다. 상근이는 결과를 출근한 첫 날부터 공책에 적어 두었다. 하지만, 엄
www.acmicpc.net
알고리즘 순서
1. 샘플의 무게를 정의하여 규칙에따라 쿼리를 통해 다른 여러 샘플들의 무게를 출력하는 문제이다.
2-1. 쿼리에서 '!'은 노드간 무게 차이를 정의하여 준다. 그래서 두 개의 노드와 거리가 나오면 두 노드에 대해서 Union을 해주면 되고 그때의 무게차이는 간선을 나타내는 벡터를 정의하여 데이터를 추가시켜주면 된다.
2-2. '?'에서 두개의 노드를 입력받는데 이때 해당 노드를 Find함수를 통해 정의가 돼 있는 노드이면 queue에 true값과 함께 해당 노드들을 push하고 Find에서 false를 return 받으면 queue에 false 와 두 노드를 push 한다.
3. 그래서 query가 끝나면 queue에서 하나씩 꺼내어 질의 처리를 해주는데 false가 나오면 UNKNOWN을 출력하면 되고 true가 나오면 이제 두 노드의 무게 차이를 구해주면 되는데 이 무게 차이를 구하기 위해서는 dfs를 활용해야 한다.
4. 주의할 점은 여러개의 트리가 만들어질 수 있기 때문에 반드시 1~n까지 노드를 탐색시켜줘야 하며 dfs 입력 파라메타로 sum값을 넣어 다음 노드 방문할때마다 앞서 정의한 무게 차이 값을 갱신해서 다음 dfs입력값으로 넘겨줘야 하고 노드를 방문할때마다 방문처리를 하여 중복방문을 하지 않게 처리해야 한다.
소스코드