[baekjoon 1922] 네트워크 연결 - 최소 스패닝 트리(크루스칼, Union-Find)

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

최소 스패닝 트리를 만들어서 간선들의 합이 최소가 되게끔 풀면 된다.

쓰인 알고리즘은 크루스칼 알고리즘과 Union-Find 알고리즘이다.

크루스칼 알고리즘을 통해 모든 Vertex를 최소의 비용으로 연결을 시키면 되고,

연결 하는 도중 싸이클이 생기지 않도록 Union-Find 알고리즘을 사용하면 된다.

 

 - 최소 스패닝 트리란?

 : 우선 스패닝 트리란 트리의 모든 노드를 포함하고, 노드끼리 연결이 되어있으며 싸이클이 발생하지 않는 트리다.

 : 여기에 최소의 뜻을 더하면 노드끼리 연결하되, 최소의 비용을 갖고 트리를 구성하는 것을 말한다.

 

-> 따라서 크루스칼(Kruskal) 알고리즘을 통해 

1. 간선들을 비용을 기준으로 오름차순 정렬

2. 가장 적은 비용이 드는 간선부터 연결

3. 연결하는 도중에 사이클이 생기는지 판단 (생기면 제외한다)

4. 2.3을 반복하며 최소 비용 스패닝 트리를 완성한다.

 

-> 여기서 Union-Find 알고리즘을 통해

1. 간선들끼리 연결할 때 노드의 parent 배열을 구성해주며

2. 크루스칼의 3번을 판별하기 위해 연결되는 간선의 노드들의 parent배열을 확인한다.

(노드들의 부모가 같다면 이미 연결되어 있다는 것이다.)

 

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

int parent[1001];

int getParent(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = getParent(parent[x]);
   // return시 parent[x] = 를 해주면서 재귀가 끝나면서 해당되는 배열을 부모값으로 업데이트 해준다.
}

void unionParent(int a, int b) {
// 여기서 int tempA = getParent(a)를 해주면 안된다.
// 받은 a를 넣어줘야 getParent(a)를 통해 return된 a가 업데이트가 된다.
// 그래야 parent[a or b ] = b or a 를 진행할 때 올바르게 부모가 업데이트 된다. 
	a = getParent(a); 
	b = getParent(b);
	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
}

bool find(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	return a == b;
}

class Edge {
public:
	int node[2];
	int distance;
	Edge(int a, int b, int distance) {
		this->node[0] = a; // node 1
		this->node[1] = b; // node 2
		this->distance = distance;
	}
	bool operator <(Edge& edge) {
		return this->distance < edge.distance;
	}
};
vector<Edge> v;
int N, M, a, b, c, sum;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		v.push_back(Edge(a, b, c));
	}
	sort(v.begin(), v.end()); // distance 비용으로 오름차순 정렬

	for (int i = 1; i <= N; i++) {
		parent[i] = i; // 부모 배열 초기화
	}

	for (int i = 0; i < v.size(); i++) {
		if (!find(v[i].node[0], v[i].node[1])) { // find함수를 통해 각 노드의 사이클 판별
			unionParent(v[i].node[0], v[i].node[1]); // 부모가 다르다면 연결해준다.
			sum += v[i].distance;
		}
	}
	cout << sum;
}