[백준][1197] 최소 스패닝 트리

이 포스트는 백준 사이트의 최소 스패닝 트리 문제 풀이입니다.

문제

해결 과정

이 문제는 Union-Find 알고리즘을 활용한 크루스칼 알고리즘으로 해결할 수 있습니다.

최소 스패닝 트리란, 주어진 그래프의 모든 정점을 연결하는 부분 그래프에서 그 가중치의 합이
최소인 트리를 의미합니다.
그리고 이 트리를 구하기 위한 크루스칼 알고리즘은
가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다.

문제에서 입력받은 간선 비용을 오름차순으로 정렬하고 아래와 같은 과정을 반복합니다.

1. 정렬 순서에 맞춰 비용을 하나씩 추가합니다.
2. 추가하기 전, 해당 간선으로 그래프에서 사이클이 발생하는지 확인합니다.
3. 간선 추가로 사이클이 발생한다면, 추가하지 않고 다음 간선으로 넘어갑니다.

Vertex 배열에서는 비용에 따라 정렬이 필요하므로
<비용, <시작노드, 도착노드»의 형태로 만들었습니다.

코드 구현

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

using namespace std;

vector<pair<int, pair<int, int>>> Vertex;

int Kruskal(int Edge, int Node);

class UnionFind;


int main() {
	int inputEdge, inputNode;
	cin >> inputNode >> inputEdge;

	int From, To, Cost;
	for (int i = 0; i < inputEdge; ++i) {
		cin >> From >> To >> Cost;
		Vertex.emplace_back(make_pair(Cost, make_pair(From, To)));
	}
	sort(Vertex.begin(), Vertex.end());

	cout << Kruskal(inputEdge, inputNode);
	return 0;
}

int Kruskal(int Edge, int Node) {
	UnionFind uf(Node);
	int answer = 0;

	for (int e = 0; e < Edge; ++e) {
		if (false == uf.SameParent(Vertex[e].second.first, Vertex[e].second.second)) {
			uf.Union(Vertex[e].second.first, Vertex[e].second.second);
			answer = answer + Vertex[e].first;
		}
	}

	return answer;
}

class UnionFind {
private:
	int inputNode;
	int* Parent;

public:
	UnionFind(int n) : inputNode(n) {
		Parent = new int[inputNode + 1];
		for (int i = 1; i <= inputNode; ++i) Parent[i] = i;
	}
	~UnionFind() {
		delete[] Parent;
	}

	int Find(int x) {
		if (x == Parent[x]) return x;
		else return Parent[x] = Find(Parent[x]);
	}

	void Union(int x, int y) {
		x = Find(x);
		y = Find(y);

		if (x != y) Parent[y] = x;
	}

	bool SameParent(int x, int y) {
		x = Find(x);
		y = Find(y);

		if (x == y) return true;
		else return false;
	}
};

실행 결과