[6일차] 그래프1 C - 1922 : 네트워크 연결

골드 Ⅳ

 

#include <iostream>
#include <queue>
using namespace std;

struct edgeInfo {
	int node1, node2, weight;
};

struct compare {
	bool operator()(const edgeInfo& edgeInfo1, const edgeInfo& edgeInfo2) {
		return edgeInfo1.weight > edgeInfo2.weight;
	}
};

priority_queue<edgeInfo, vector<edgeInfo>, compare>min_heap;
int N, M;
int parent[1001];

int find(int node) {
	if (parent[node] == node) return node;
	return parent[node] = find(parent[node]);
}

void uni(int node1, int node2) {
	parent[find(node1)] = find(node2);
}

int main() {
	scanf("%d%d", &N, &M);
	//parent 배열 초기화
	for (int i = 1; i <= N; i++) parent[i] = i;

	//정보 입력받기
	int a, b, c;
	while (M--) {
		scanf("%d%d%d", &a, &b, &c);
		min_heap.push({ a, b, c });
	}

	int connectCnt = 0;
	int weightSum = 0;
	//크루스칼 알고리즘 진행
	while (true) {
		if (connectCnt == N - 1) break;
		edgeInfo e = min_heap.top();
		min_heap.pop();
		//둘이 사이클을 안 만든다면
		if (find(e.node1) != find(e.node2)) {
			//이어줌
			uni(e.node1, e.node2);
			//간선 개수 증가
			connectCnt++;
			//가중치 더해주기
			weightSum += e.weight;
		}
	}
	printf("%d", weightSum);
}

 

크루스칼 알고리즘

(= 최소 스패닝 트리(=MST) 구하는 알고리즘)

(= union-find 사용)

간선들이 중심이 되는 알고리즘. 따라서

노드보다 간선들이 적을 때 유용