[C++] 최소비용신장트리 - kruskal 알고리즘

최소비용신장트리는 순환하지 않는 최소 비용의 경로를 의미한다. kruskal 알고리즘은 그리디 알고리즘이며 합집합 찾기가 이 알고리즘의 핵심이다. 사실 알고리즘 자체는 굉장히 간단하다. 아래의 세 단계만 거치면 된다.

​

1. 비용을 기준으로 오름차순 정렬한다.
2. 순환하지 않도록 최소 비용순으로 노드를 선택한다. 이때 Union-Find 알고리즘을 사용한다.
3. 모든 노드를 선택할때까지 2번을 반복한다.

 

사실 합집합 찾기만 알면 너무 간단한 문제라서 크게 설명할 건 없다. Edge 클래스를 정의해 주고 연산자 오버로딩만 해주면 된다. 그 외에는 위의 세 단계만 코드로 구현하면 된다. 코드가 이해가지 않으면 Union-Find 파트를 다시 읽어보자. 아래 코드는 '프로그래머스 - 섬 연결하기' 문제 정답 코드다.

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

class Edge {
public:
	int node[2];
	int distance;
	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]);
}

// 두 노드 연결
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 findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1;
	return 0;
}

int solution(int n, vector<vector<int>> costs) {
	int* parent = new int[n]; // 부모 노드 배열
	vector<Edge> edge;
	for (int i = 0; i < n; i++)
		parent[i] = i;

	for (vector<int> vec : costs) 
		edge.push_back(Edge(vec[0], vec[1], vec[2]));
	
	sort(edge.begin(), edge.end());

	int sum = 0;
	for (int i = 0; i < costs.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() {
	vector<vector<int>> a = { {0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8} };
	cout << solution(4, a);

	return 0;
}