[C++] 원더랜드(Kruskal MST 알고리즘 : Union&Find 활용) ⭐

크루스칼(Kruskal) 알고리즘을 사용하여 그래프의 최소 신장 트리(Minimum Spanning Tree)를 찾습니다.

최소 신장 트리는 그래프의 모든 노드를 포함하면서 모든 노드를 연결하는 데 필요한 간선 중에서 가중치의 합이 최소인 트리입니다.

 

📄문제

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 어떤 도로는 도로를 유지보수하면 재정에 도움이 되는 도로도 존재한다. 재정에 도움이 되는 도로는 비용을 음수로 표현했다.
아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

 

⬇️ 입력

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

9 12 1 2 12 1 9 25 2 3 10 2 8 17 2 9 8 3 4 18 3 7 55 4 5 44 5 6 60 5 7 38 7 8 35 8 9 15

 

⬆️ 출력

모든 도시를 연결하면서 드는 최소비용을 출력한다.

196

 

📝 풀이

#include <iostream>
#include <queue>
using namespace std;

// Union-Find에서 집합 정보를 저장할 배열
int arr[1001];

// Find
int Find(int n)
{
	if (n == arr[n]) return n;
	else return arr[n] = Find(arr[n]);
}

// Union
void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (a != b)
		arr[a] = b;
}

int main()
{
	int N, M, f, t, w, res = 0;
	scanf_s("%d %d", &N, &M);

	// 우선순위 큐를 사용하여 더욱 효율적으로 정렬
	priority_queue<pair<int, pair<int, int>>> q; // -가중치, 출발, 도착
	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d %d", &f, &t, &w);
		q.push({ -w, {f, t} });
	}

	// 집합 정보 초기화
	for (int i = 1; i <= N; ++i)
		arr[i] = i;

	// 모든 간선 정보를 사용
	while (!q.empty())
	{
		// 가장 비용이 낮은 간선 정보를 가져오기 
		pair<int, pair<int, int>> data = q.top();
		q.pop();

		// 정보 추출
		int weight = -data.first;
		int from = data.second.first;
		int to = data.second.second;

		// 간선의 집합 정보 가져오기
		int a = Find(from);
		int b = Find(to);

		// 서로 다른 집합이라면?
		if (a != b)
		{
			// 가중치를 합하고, 결합
			res += weight;
			Union(from, to);
		}
	}

	printf("%d", res);
}

• Union-Find를 이용하여 해결합니다.
• 간선의 정보를 가중치를 기준으로 오름차순 정렬합니다.
• 오름차순 정렬 된 상태에서, 가장 비용이 적은 top을 하나씩 가져와 다른 노드와 연결을 시도합니다.
• 만약 from, to가 union에 의해 서로 같은 조합에 있다면 연결을 하지 않습니다(loop 방지)
• 서로 다른 조합에 있다면, 연결합니다.
• 모든 간선 정보를 사용하여 결과를 출력합니다.