[ 백준 1197 ] 최소 스패닝 트리 (C++)

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

1197번: 최소 스패닝 트리

 

문제 제목에서 친절하게 어떤 문제인지 알려주고 있다. 나는 크루스칼 알고리즘으로 문제를 풀었다. 크루스칼 알고리즘은 알고리즘 파트에서 확인할 수 있으며 코드 구성도 거의 동일하다. 링크 바로가기!

 

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

class Edge {
public:
	int distance;
	int node[2];
	Edge(int _a, int _b, int _distance) {
		this->node[0] = _a;
		this->node[1] = _b;
		this->distance = _distance;
	}

	bool operator<(Edge& edge) {
		return this->distance < edge.distance;
	}
};

int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}

int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1;
	return 0;
}

void unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

int kruskal(int n, int size, int** graph ) {
	int* parent = new int[n];
	for (int i = 0; i < n; i++)
		parent[i] = i;

	vector<Edge> edge;

	for (int i = 0; i < size; i++)
		edge.push_back(Edge(graph[i][0], graph[i][1], graph[i][2]));

	sort(edge.begin(), edge.end());

	int sum = 0;

    // 모든 간선에 대해서 부모가 다르면 union, 같으면 pass
	for (int i = 0; i < size; i++) {
		if (!findParent(parent, edge[i].node[0], edge[i].node[1])) {
			sum += edge[i].distance;
			unionParent(parent, edge[i].node[0], edge[i].node[1]);
		}
	}

	return sum;
}

int main() {
	int V, E;
	int a, b, dist;
	cin >> V >> E;

	int** graph = new int*[E];
	for (int i = 0; i < E; i++)
		graph[i] = new int[3];

	for (int i = 0; i < E; i++) {
		cin >> a >> b >> dist;
		graph[i][0] = a - 1;
		graph[i][1] = b - 1;
		graph[i][2] = dist;
	}

	cout << kruskal(V, E, graph);

	for (int i = 0; i < E; i++)
		delete[] graph[i];
	delete[] graph;

	return 0;
}