[백준 C++] 1197 최소 스패닝 트리 - 최소신장트리

1197번: 최소 스패닝 트리

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> EdgeList;
vector<int> RootNode;

bool Compare(const vector<int>& Left, const vector<int>& Right)
{
	return (Left[2] < Right[2]);
}

int Find(int Node)
{
	if (Node != RootNode[Node])
	{
		RootNode[Node] = Find(RootNode[Node]);
	}

	return RootNode[Node];
}

bool Union(int NodeA, int NodeB)
{
	int RootA = Find(NodeA);
	int RootB = Find(NodeB);

	if (RootA == RootB)
	{
		return false;
	}

	int MinRoot = min(RootA, RootB);
	RootNode[RootA] = MinRoot;
	RootNode[RootB] = MinRoot;

	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int V, E;
	cin >> V >> E;

	EdgeList.reserve(E);
	for (int i = 0; i < E; ++i)
	{
		EdgeList.emplace_back(vector<int>(3, 0));

		int Start, End, Weight;
		cin >> Start >> End >> Weight;

		EdgeList.back()[0] = Start - 1;
		EdgeList.back()[1] = End - 1;
		EdgeList.back()[2] = Weight;
	}

	sort(EdgeList.begin(), EdgeList.end(), Compare);

	RootNode.reserve(V);
	for (int i = 0; i < V; ++i)
	{
		RootNode.emplace_back(i);
	}

	int Sum = 0;
	int Cnt = 0;
	int Current = 0;
	while (Cnt < V - 1)
	{
		int Start = EdgeList[Current][0];
		int End = EdgeList[Current][1];

		if (Union(Start, End))
		{
			int Weight = EdgeList[Current][2];
			Sum += Weight;
			++Cnt;
		}

		++Current;
	}

	cout << Sum;
}

---

크루스칼 알고리즘으로 풀었습니다.

풀이 과정은 다음과 같습니다.

 

1. 에지 리스트로 그래프 구현 & 유니온 파인드 리스트 초기화
2. 에지 리스트를 가중치 오름차순으로 정렬
3. 가중치가 낮은 에지부터 연결 시도 - 파인드 연산을 통해 서로 다른 집합임을 판별했을 때(루트노드가 서로 다름)만 연결
4. N-1개의 에지가 연결될 때까지 3번 반복 -> 연결된 에지 개수 & 비용 합 카운트
5. 총 에지 비용 출력