[c++/백준] 1197번: 최소 스패닝 트리

문제 링크

1197번: 최소 스패닝 트리

풀이

크루스칼을 이용하는 문제
최소 신장 트리란 사이클 없는 트리 중 가중치의 값이 가장 작은 신장 트리를 말한다.
알고리즘으로 크루스칼과 프림이 있는데, 난 크루스칼을 이용하였다.
가중치 기준으로 오름차순 정렬해서 두 노드가 같은 그래프가 아니면 잇는 방식이다.
두 노드가 같은지 확인하는 same함수와 합치는 함수 unite는 유니온 파인드를 사용한다.

1. 먼저 가중치 기준으로 costs를 오름차순 정렬을 한다.
2. 대푯값이 저장되는 vector link와, 대푯값의 집합 크기를 저장하는 vector size를 초기화한다. 처음에는 각 노드가 연결되어 있지 않은 상태이므로, 각 노드의 대푯값은 자기 자신이며, 집합 크기 또한 자기 자신 1개이다.
3. 정렬된 costs를 모두 살펴보며 노드 a와 노드 b가 같은 집합인지 확인해서, 같은 집합(그래프)가 아니면 합친다.
   3-1. 같은 집합인지 확인하는 함수 same은 대푯값을 찾는 함수 find를 이용해 return한다. find함수는 탐색하는 노드가 대푯값과 같지 않으면 그 노드는 대푯값이 아니라는 뜻이므로 같을 때까지 찾아서 return한다.
   3-2. 집합을 합치는 함수 unite는 매개변수로 받은 노드 두개의 대푯값을 찾아 합치는데, 원소의 수가 많은 쪽으로 합친다. 합칠 경우 대푯값과 집합 크기가 변하므로 이에 맞게 갱신해준다.
4. 함수를 합칠 때마다 가중치가 저장되므로 모든 간선 체크가 끝나면 최소 가중치 값이 나올 것이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> link;
vector<int> cnt;

bool comp(vector<int> a, vector<int> b)
{
	return a[2] < b[2];
}

int find(int x) // 대표값 찾기
{
	while (x != link[x]) x = link[x];
	return x;
}

bool same(int a, int b) // 집합이 같은지 확인
{
	return find(a) == find(b);
}

void unite(int a, int b) // 집합 합치기
{
	a = find(a);
	b = find(b);
	if (cnt[a] < cnt[b]) swap(a, b);
	cnt[a] += cnt[b];
	link[b] = a;
}

int main(void)
{
	int answer = 0;

	int v, e;
	cin >> v >> e;

	vector<vector<int>> costs(e,vector<int>(3));
	for (int i = 0; i < e; i++)
	{
		cin >> costs[i][0] >> costs[i][1] >> costs[i][2];
	}

	sort(costs.begin(), costs.end(), comp);

	for (int i = 0; i <= v; i++) link.push_back(i);
	for (int i = 0; i <= v; i++) cnt.push_back(0);

	for (int i = 0; i < costs.size(); i++)
	{
		int a = costs[i][0];
		int b = costs[i][1];
		int cost = costs[i][2];
		if (!same(a, b))
		{
			answer+=cost;
			unite(a, b);
		}
	}

	cout << answer << endl;

	return 0;
}