백준1197 - 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

나동빈님의 알고리즘 강좌를 참고하여 만들었다. 최소 스패닝 트리는 크루스칼 알고리즘을 사용한다. 크루스칼 알고리즘은 공통조상을 찾는 과정이 들어가야 한다. 공통조상을 찾는 과정 후에 임의의 지점 a와 b의 부모가 같지 않으면 최소 스패닝 비용에 a에서 b로 이동하는 비용을 더하고 a와 b의 부모를 찾는 과정이 이루어진다.

 

크루스칼 알고리즘을 공부하면서 플루이드와샬알고리즘과 다익스트라알고리즘으로 풀지 못한 문제를 다시 보게 되었다. 코드가 간단하지만 정말 유용한 알고리즘이니 꼭 숙지해야겠다.

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

//a에서 b로 가는 비용을 저장할 클래스 
class Edge {
public:
	int node[2]; //a(node[0])와 b(node[1])의 정보
	int distance; //a->b로 가는 비용
	
	//a와 b사이의 비용을 저장하기 위해 설정한 생성자
	Edge(int a, int b, int distance) {
		this->node[0] = a;
		this->node[1] = b;
		this->distance = distance;
	}

	//객체의 정보를 가지고 오름차순을 하기 위해 연산자 오버로딩
	bool operator < (Edge & e) {
		return this->distance < e.distance;
	}
};

//x에 부모를 찾기 위한 과정을 구현
int getParent(int parent[], int x) {
	if (parent[x] == x) { //입력된 수의 부모가 자기 자신이면
		return x; //반환
	}
	return parent[x] = getParent(parent, parent[x]); //최종 부모를 찾는 과정
}

//부모를 합치는 과정, 숫자가 작은 것이 부모가 되게 설정
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;
	}
}

//부모가 같은지 확인하는 과정, 부모가 같으면 true, 부모가 다르면 false
bool findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	int n, m; //n은 노드의 갯수, m은 경로의 갯수
	int a, b, distance; //a에서 b로 가는데 distance의 비용이 든다.
	int sum = 0; //최소 스패닝 트리에 경로 합
	int parent[10001]; //각 그래프에 최고 조상이 누구인지 저장
	vector<Edge> v; //a->b로 갔을 때 비용을 담는 클래스
	
	cin >> n >> m;

	//m개의 a->bf로 가는 비용 distance를 입력
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> distance;
		v.push_back(Edge(a, b, distance));
	}

	sort(v.begin(), v.end()); //비욜을 기준으로 오름차순 정렬

	//처음에는 자기 자신이 부모인 것으로 설정
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	//최소 스패닝 트리를 제작하는 과정, a와 b의 부모가 같지 않으면 distance를 더하고 a와 b의 동일한 부모를 찾는다. 부모가 같으면 비용을 더하지 않는다.
	for (int i = 0; i < v.size(); i++) {
		if (!findParent(parent, v[i].node[0], v[i].node[1])) {
			sum += v[i].distance;
			unionParent(parent, v[i].node[0], v[i].node[1]);
		}
	}

	cout << sum;
}