최소 신장 트리(Mininum Spanning Tree)

최소 신장 트리?

백준 1922번 : 네트워크 연결

평소처럼 알고리즘 문제를 하나 풀어보려고 읽어보니,
그래프를 사용하는 문제였다.

기존에 내가 알고있던 그래프 알고리즘은
다익스트라 알고리즘과 플로이드-워셜 알고리즘이었는데,
문제를 아무리 쳐다보고 있어도 위 알고리즘들과는 거리가 멀어보였다.

그리하여 힌트를 얻고자 분류를 살짝 열어보니 최소 신장 트리라는
처음보는 알고리즘으로 분류되어 있었다.

이럴 땐 이론을 검색해보고 구현은 직접하자! 라는 생각을 갖고있기 때문에
구글을 통해 대략적인 개념을 살펴보았다.

내가 해결하고자 하는 문제가 최소 신장 트리의 이론을 그대로 옮겨서 문제로 표현한 것이었다.

노드의 갯수와 각 노드들을 연결하는 간선들의 종류 및 비용이 주어졌을 때,
최소비용으로 모든 노드를 공유시키는 것

으로 정리할 수 있을 것 같다.

그 중에서도 프림 알고리즘과 크루스칼 알고리즘 두가지 방법을 봤는데,
나는 크루스칼알고리즘을 사용하는 쪽이 더 좋을 것 같았다.

크루스칼 알고리즘

전체적인 과정은 이러했다. (노드 : N개, 간선 : M개)

1. 모든 간선을 비용을 기준으로 오름차순으로 정렬한다.
2. 모든 간선을 비용이 낮은 순으로 반복하여 다음의 검사를 시행한다.
3. 간선의 양 끝이 가리키는 노드가 서로 이미 공유 중인가 판단한다. (사이클을 만들지 않는다.)
4. 공유 중이라면 무시한채 다음 간선으로 넘어가고, 공유 중이지 않다면 해당 간선을 확정한다. (이 문제에서는 출력값에 더해줬다.)
5. N개의 노드를 서로 공유하기 위해서는 N-1개의 간선만 있으면 되기 때문에, N-1개의 간선이 확정된 순간 반복문을 종료한다. 기존에 간선의 비용에 맞추어 오름차순으로 정렬했기 때문에, 간선이 모두 확정된 순간이 최소비용이다.

문제에서의 활용

크루스칼 알고리즘을 정말 똑같이 구현하기만 하면 문제를 해결할 수 있었다.

간선의 양 끝의 노드가 이미 공유 중인지 판단하기 위해 Union-find 자료구조를 사용했다.
다른 문제를 해결하면서 한번 배워둔 적이 있는데, 어렵지 않아서 바로 활용할 수 있었다!!