[백준 1922번 C++] 네트워크 연결

대표적인 Union-find 알고리즘과 크루스칼 알고리즘 문제다. 

비슷한 문제로는 백준 1197번 최소 스패닝 트리 문제(https://www.acmicpc.net/problem/1197)가 있다.

최소 스패닝  트리 문제는 지난번에 풀어놨으니 참고하면 될 듯하다. 

https://yuldangs-sosolife.tistory.com/entry/%EB%B0%B1%EC%A4%80-1197%EB%B2%88-C-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC

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

 

크루스칼 알고리즘을 구현할 수 있다면 간단히 풀 수 있다. 

#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;
	}
};

vector<Edge> network;
int parent[1001];

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

void Union(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	if (a < b) parent[b] = a;
	else parent[a] = b;
}

bool findParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	if (a == b) return true;
	else return false;
}

int main() {
	int N, M, u, v, w;
	int answer = 0;
	
	cin >> N >> M;

	for (int i = 0; i <= N; i++) parent[i] = i;

	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		network.push_back(Edge(u, v, w));
	}

	sort(network.begin(), network.end());
	
	for (int i = 0; i < network.size(); i++) {
		if (!findParent(network[i].node[0], network[i].node[1])) {
			answer += network[i].distance;
			Union(network[i].node[0], network[i].node[1]);
		}
	}

		cout << answer << "\n";
}