[Baekjoon] 1197번: 최소 스패닝 트리

 

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

---

 

문제 해결 과정

착안

최소 (비용) 신장 트리(minimum spanning tree, MST)를 구하는 문제이므로, 이를 구하는 대표적인 알고리즘을 이용하여 문제를 해결하고자 하였다. 문제에서 한 줄씩 간선 데이터를 입력으로 제공하기 때문에, 간선 데이터를 하나씩 저장하면서 정렬하는 것이 문제 해결에 편리할 것 같아서 크루스칼 알고리즘(Kruskal's algorithm)을 사용하고자 하였다.

 

구현

크루스칼 알고리즘을 사용하기 위해, 편의상 간단히 서로소 집합(분리 집합) 자료 구조를 나타내기 위한 함수를 구현했다. 한편 간선 정렬에 사용할 우선순위 큐는 STL의 컨테이너인 std::priority_queue<> 클래스를 활용하여 구현하고, 가중치가 낮은 순으로 간선을 정렬하기 위해 별도로 이항 조건을 만들어 사용하였다(디폴트: 오름차순 $\longrightarrow$ 가중치가 큰 순으로 정렬).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>

using namespace std;

struct Edge	{ int From, Dest, Weight; };
struct cmp	{ bool operator()(Edge a, Edge b) const { return a.Weight > b.Weight; } };

priority_queue<Edge, vector<Edge>, cmp> Edges;
int Verticies[10000];

int Find(int a)
{
	if (a == Verticies[a])
		return a;

	return Verticies[a] = Find(Verticies[a]);
}

void Union(int a, int b)
{
	if (a == b)
		return;

	int pa = Find(a);
	int pb = Find(b);
	if (pa == pb)
		return;

	Verticies[pb] = a;
}

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

	int V, E, TotalWeight = 0;
	cin >> V >> E;

	for (int i = 0; i < V; i++)
		Verticies[i] = i;

	while (E--)
	{
		int from, dest, weight;
		cin >> from >> dest >> weight;
		Edges.emplace(Edge{ from - 1, dest - 1, weight });
	}

	while (!Edges.empty())
	{
		Edge edge = Edges.top();
		Edges.pop();

		if (Find(edge.From) == Find(edge.Dest))
			continue;

		Union(edge.From, edge.Dest);
		TotalWeight += edge.Weight;
	}

	cout << TotalWeight << "\n";
	return 0;
}

 

실행 결과