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

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[9][9], ans = INT_MAX;
vector<pair<int, int> > cctv;

void up(int arr[][9], int x, int y) {
	for (int i = x - 1; i >= 0; i--) {

		if (arr[i][y] == 0) {
			arr[i][y] = -1;
		}
		else if (arr[i][y] == 6) {
			break;
		}
	}
}

void down(int arr[][9], int x, int y) {
	for (int i = x + 1; i < n; i++) {
		if (arr[i][y] == 0) {
			arr[i][y] = -1;
		}
		else if (arr[i][y] == 6) {
			break;
		}
	}
}

void Left(int arr[][9], int x, int y) {
	for (int i = y - 1; i >= 0; i--) {
		if (arr[x][i] == 0) {
			arr[x][i] = -1;
		}
		else if (arr[x][i] == 6) {
			break;
		}
	}

}

void Right(int arr[][9], int x, int y) {
	for (int i = y + 1; i < m; i++) {
		if (arr[x][i] == 0) {
			arr[x][i] = -1;
		}
		else if (arr[x][i] == 6) {
			break;
		}
	}

}

void arr_init(int tmp[][9], int arr[][9]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tmp[i][j] = arr[i][j];
		}
	}

}

void DFS(int arr[][9], int L) {

	int tmp[9][9];
	arr_init(tmp, arr);

	if (L == cctv.size()) {

		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 0) {
					cnt++;
				}
			}
		}
		ans = min(cnt, ans);

		return;

	}
	else {
		int x = cctv[L].first;
		int y = cctv[L].second;

		if (arr[x][y] == 1) {
			up(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			down(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			Left(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

		}
		else if (arr[x][y] == 2) {
			up(tmp, x, y);
			down(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			Left(tmp, x, y);
			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

		}
		else if (arr[x][y] == 3) {
			up(tmp, x, y);
			Left(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			up(tmp, x, y);
			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			down(tmp, x, y);
			Left(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			down(tmp, x, y);
			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);
		}
		else if (arr[x][y] == 4) {
			up(tmp, x, y);
			down(tmp, x, y);
			Left(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			up(tmp, x, y);
			down(tmp, x, y);
			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);

			up(tmp, x, y);
			Left(tmp, x, y);
			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);


			down(tmp, x, y);
			Left(tmp, x, y);
			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);
		}
		else if (arr[x][y] == 5) {
			up(tmp, x, y);
			down(tmp, x, y);
			Left(tmp, x, y);
			Right(tmp, x, y);
			DFS(tmp, L + 1);
			arr_init(tmp, arr);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];

			if (arr[i][j] > 0 && arr[i][j] <= 5) {
				cctv.push_back({ i,j });
			}
		}
	}


	DFS(arr, 0);


	cout << ans << '\n';

	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n, arr[21][21], ans = 0;



void print(int arr[][21]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}

	cout << "---------------------------------\n";
	return;
}

void up(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = i-1;

				while ((p - 1 >= 0) && (arr_[p][j] == 0)) {
					p--;
				}

				if (arr_[p][j] == 0) {
					swap(arr_[i][j], arr_[p][j]);
				}
				else {
					if ((arr_[p][j] == arr_[i][j]) && (merged[p][j] == 0)) {
						merged[p][j] = 1;
						arr_[p][j] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[p + 1][j]);
					}
				}
			}
		}
	}
}



void down(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = n-2; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = i + 1;

				while ((p + 1 <= n - 1) && (arr_[p][j] == 0)) {
					p++;
				}

				if (arr_[p][j] == 0) {
					swap(arr_[i][j], arr_[p][j]);
				}
				else {
					if ((arr_[p][j] == arr_[i][j]) && (merged[p][j] == 0)) {
						merged[p][j] = 1;
						arr_[p][j] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[p - 1][j]);
					}
				}

			
			}
		}
	}
}


void Left(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = j - 1;

				while ((p - 1 >= 0) && (arr_[i][p] == 0)) {
					p--;
				}

				if (arr_[i][p] == 0) {
					swap(arr_[i][p], arr_[i][j]);
				}
				else {
					if ((arr_[i][p] == arr_[i][j]) && (merged[i][p] == 0)) {
						merged[i][p] = 1;
						arr_[i][p] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[i][p+1]);
					}
				}


			}
		}
	}
}



void Right(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 0; i < n; i++) {
		for (int j = n - 2; j >= 0; j--) {
			if (arr_[i][j] > 0) {
				int p = j + 1;

				while ((p + 1 <= n - 1) && (arr_[i][p] == 0)) {
					p++;
				}

				if (arr_[i][p] == 0) {
					swap(arr_[i][p], arr_[i][j]);
				}
				else {
					if ((arr_[i][p] == arr_[i][j]) && (merged[i][p] == 0)) {
						merged[i][p] = 1;
						arr_[i][p] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[i][p-1]);
					}
				}

			}
		}
	}
}


void copyArray(int arr_[][21], int arr[][21]) {
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			arr_[i][j] = arr[i][j];
		}
	}
}

void DFS(int arr[][21], int L) {

	int arr_[21][21];
	copyArray(arr_, arr);

	if (L == 5) {
		int maxx = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				maxx = max(arr[i][j], maxx);
			}
		}
		ans = max(ans, maxx);

	}
	else {
		up(arr_);
		DFS(arr_, L + 1);

		copyArray(arr_, arr);
		down(arr_);
		DFS(arr_, L + 1);


		copyArray(arr_, arr);
		Left(arr_);
		DFS(arr_, L + 1);

		copyArray(arr_, arr);
		Right(arr_);
		DFS(arr_, L + 1);

	}
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}


	DFS(arr, 0);




	cout << ans << '\n';
	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n, arr[21][21], ans = 0, real_ans=0;
int L_max[11];

void up(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = i-1;

				while ((p - 1 >= 0) && (arr_[p][j] == 0)) {
					p--;
				}

				if (arr_[p][j] == 0) {
					swap(arr_[i][j], arr_[p][j]);
				}
				else {
					if ((arr_[p][j] == arr_[i][j]) && (merged[p][j] == 0)) {
						merged[p][j] = 1;
						arr_[p][j] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[p + 1][j]);
					}
				}
			}
		}
	}
}


void down(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = n-2; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = i + 1;

				while ((p + 1 <= n - 1) && (arr_[p][j] == 0)) {
					p++;
				}

				if (arr_[p][j] == 0) {
					swap(arr_[i][j], arr_[p][j]);
				}
				else {
					if ((arr_[p][j] == arr_[i][j]) && (merged[p][j] == 0)) {
						merged[p][j] = 1;
						arr_[p][j] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[p - 1][j]);
					}
				}
			}
		}
	}
}


void Left(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (arr_[i][j] > 0) {
				int p = j - 1;

				while ((p - 1 >= 0) && (arr_[i][p] == 0)) {
					p--;
				}

				if (arr_[i][p] == 0) {
					swap(arr_[i][p], arr_[i][j]);
				}
				else {
					if ((arr_[i][p] == arr_[i][j]) && (merged[i][p] == 0)) {
						merged[i][p] = 1;
						arr_[i][p] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[i][p+1]);
					}
				}
			}
		}
	}
}


void Right(int arr_[][21]) {
	bool merged[21][21];
	memset(merged, 0, sizeof(merged));
	for (int i = 0; i < n; i++) {
		for (int j = n - 2; j >= 0; j--) {
			if (arr_[i][j] > 0) {
				int p = j + 1;

				while ((p + 1 <= n - 1) && (arr_[i][p] == 0)) {
					p++;
				}

				if (arr_[i][p] == 0) {
					swap(arr_[i][p], arr_[i][j]);
				}
				else {
					if ((arr_[i][p] == arr_[i][j]) && (merged[i][p] == 0)) {
						merged[i][p] = 1;
						arr_[i][p] *= 2;
						arr_[i][j] = 0;
					}
					else {
						swap(arr_[i][j], arr_[i][p-1]);
					}
				}

			}
		}
	}
}

void copyArray(int arr_[][21], int arr[][21]) {
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			arr_[i][j] = arr[i][j];
		}
	}
}

bool isdif(int arr_[][21], int arr[][21]){
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			if (arr_[i][j] != arr[i][j]) {
				return true;
			}
		}
	}
	return false;
}


void DFS(int arr[][21], int L) {
	int arr_[21][21];
	copyArray(arr_, arr);

	int maxx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			maxx = max(arr[i][j], maxx);
		}
	}

	if (maxx <= L_max[L]) {
		return;
	}

	real_ans = max(real_ans, maxx);

	if (L == 10) {
		if (ans < maxx) {
			ans = maxx;

			int tmp = ans;
			while (L > 0) {
				L_max[L--] = tmp;
				tmp /= 2;
			}
		}
		return;
	}


	else {
		up(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);

		copyArray(arr_, arr);
		down(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);

		copyArray(arr_, arr);
		Left(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);

		copyArray(arr_, arr);
		Right(arr_);
		if (isdif(arr_, arr)) DFS(arr_, L + 1);
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	DFS(arr, 0);

	cout << real_ans << '\n';


	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;


vector<char> elec;
vector<pair<int, int> > graph[1001];

struct Edge {
	int x, val;
	bool operator<(const Edge& b) const {
		return val > b.val;
	}
};

bool vis[1001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, k;
	cin >> n >> m >> k;

	priority_queue<Edge> Q;


	for (int i = 0; i < k; i++) {
		int c;
		cin >> c;
		Q.push({ c,0 });
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
		graph[b].push_back({ a,c });
	}

	int ans = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int val = Q.top().val;
		Q.pop();

		if (vis[x] == 0) {
			vis[x] = 1;
			ans += val;

			for (int i = 0; i < graph[x].size(); i++) {
				int nx = graph[x][i].first;
				int nd = graph[x][i].second;

				if (vis[nx] == 0) {
					Q.push({ nx,nd });
				}
			}
		}
	}

	cout << ans << '\n';
	

	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int unf[1001];

int Find(int x) {
	if (x == unf[x]) {
		return x;
	}
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		unf[a] = b;
	}
}

struct Edge {
	int x, y;
	double val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

double distance(int x1, int y1, int x2, int y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	priority_queue<Edge> Q;
	for (int i = 0; i < 1001; i++) {
		unf[i] = i;
	}

	vector<pair<int,int> > v;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a, b });
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		Union(a-1, b-1);
	}


	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			double dist = distance(v[i].first, v[i].second, v[j].first, v[j].second);
			Q.push({ i,j,dist });
		}
	}

	double ans = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		double val = Q.top().val;
		Q.pop();

		if (Find(x) != Find(y)) {
			Union(x, y);
			ans += val;
		}
	}

	cout << fixed;
	cout.precision(2);
	cout << ans << '\n';

	return 0;
}

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

문제풀이

1. 섬들을 BFS를 이용해 번호를 붙여준다.

2. 번호를 붙여진 섬들간의 간선의 길이를 구한다

3. 크루스칼 알고리즘을 이용해 최소스패닝트리의 가중치를 구한다.

#include <bits/stdc++.h>
using namespace std;

int unf[7];

int Find(int x) {
	if (x == unf[x]) {
		return x;
	}
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		unf[a] = b;
	}
}

struct Edge {
	int x, y, val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};


int n, m;

bool arr_[11][11];
int arr[11][11];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int cnt = 1;

priority_queue<Edge> Kruskal;


void make_island() {
	queue<pair<int,int> > Q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr_[i][j] && arr[i][j] == 0) {
				arr[i][j] = cnt;
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();


					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr_[nx][ny] == 0 || arr[nx][ny] > 0) continue;
						arr[nx][ny] = cnt;
						Q.push({ nx,ny });
					}
				}
				cnt++;
			}
		}
	}

	return;
}


void make_edge() {
	for (int i = 0; i < n; i++) {
		int start = 0, end = 0, dist = 0;
		for (int j = 0; j < m; j++) {
			if (arr[i][j] != 0) {
				if (start == 0) {
					start = arr[i][j];
					dist = 0;
				}
				else {
					if (arr[i][j] == start) {
						dist = 0;
					}
					else {
						end = arr[i][j];
						if (dist >= 2) Kruskal.push({ start,end,dist });
						start = end;
						end = 0;
						dist = 0;
					}
				}
			}
			else if (arr[i][j] == 0) {
				dist++;
			}
		}
	}

	for (int i = 0; i < m; i++) {
		int start = 0, end = 0, dist = 0;
		for (int j = 0; j < n; j++) {
			if (arr[j][i] != 0) {
				if (start == 0) {
					start = arr[j][i];
					dist = 0;
				}
				else {
					if (arr[j][i] == start) {
						dist = 0;
					}
					else {
						end = arr[j][i];
						if (dist >= 2) Kruskal.push({ start,end,dist });
						start = end;
						end = 0;
						dist = 0;
					}
				}
			}
			else if (arr[j][i] == 0) {
				dist++;
			}
		}
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	for (int i = 0; i < 7; i++) {
		unf[i] = i;
	}

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr_[i][j];
		}
	}
	
	make_island();

	make_edge();

	int ans = 0;
	while (!Kruskal.empty()) {
		int x = Kruskal.top().x;
		int y = Kruskal.top().y;
		int val = Kruskal.top().val;
		Kruskal.pop();

		if (Find(x) != Find(y)) {
			Union(x, y);
			ans += val;
		}
	}

	int comp = Find(1);
	for (int i = 1; i <= cnt-1; i++) {
		if (comp != Find(i)) {
			cout << -1 << '\n';
			return 0;
		}
	}

	cout << ans << '\n';

	return 0;
}

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

1.문제설명

두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

INPUT

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

OUTPUT

4

INPUT으로 N개의 행성의 x,y,z 좌표가 주어진다.

좌표를 바탕으로 최소 스패닝 트리를 만들어야한다.

단 간선의 길이가  min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

2. 접근방법[알고리즘]

처음에 간선의 길이가 두 행성간 유클리드 거리인줄 알고 한참 고민했다.

이 문제에서 간선의 길이는 x좌표의 차이, y좌표의 차이, z 좌표의 차이 중 최솟값이다.

x,y,z 좌표를 각각 입력받고 sort하면 n이 10만이므로 nlogn으로 해결 할 수 있다.

그리고 각각 x좌표의 차이 y좌표의 차이 z좌표의 차이를

우선순위 큐에 넣고 Union & Find 해주면서

크루스칼 알고리즘의 방법으로 최소스패닝트리를 구할 수 있다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int unf[100001];

int Find(int x) {
	if (x == unf[x]) {
		return x;
	}
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		unf[a] = b;
	}
}

struct Edge {
	int x, y, val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

vector<pair<int, int> > x, y, z;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 100001; i++) {
		unf[i] = i;
	}

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		x.push_back({ a,i });
		y.push_back({ b,i });
		z.push_back({ c,i });
	}

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());

	priority_queue<Edge> Q;

	for (int i = 0; i < n - 1; i++) {
		int dif_x = x[i + 1].first - x[i].first;
		int dif_y = y[i + 1].first - y[i].first;
		int dif_z = z[i + 1].first - z[i].first;
		Q.push({ x[i + 1].second, x[i].second, dif_x });
		Q.push({ y[i + 1].second, y[i].second, dif_y });
		Q.push({ z[i + 1].second, z[i].second, dif_z });
	}

	int ans = 0;
	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int val = Q.top().val;
		Q.pop();

		if (Find(x) != Find(y)) {
			Union(x, y);
			ans += val;
		}
	}

	cout << ans << '\n';

	return 0;
}

크루스칼 알고리즘과 프림 알고리즘 비교

크루스칼 알고리즘은 간선을 기준으로 Spanning Tree를 연결하고

프림 알고리즘은 정점을 기준으로 Spannig Tree를 연결한다.

따라서 간선이 많을 경우 프림 알고리즘을

간선이 적을 경우 크루스칼 알고리즘을 이용하는 게 유리하다.

크루스칼 알고리즘

크루스칼 알고리즘의 시간복잡도는 간선을 Sort하는데

최대 O(ElogE)가 필요하다

#include <bits/stdc++.h>
using namespace std;

int unf[10001];

int Find(int x) {
	if (x == unf[x]) {
		return x;
	}
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		unf[a] = b;
	}
}

struct Edge {
	int x, y, val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 10001; i++) {
		unf[i] = i;
	}

	priority_queue<Edge> Q;

	int V, E;
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		Q.push({ a,b,c });
	}

	int ans = 0;
	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int val = Q.top().val;
		Q.pop();

		if (Find(x) != Find(y)) {
			Union(x, y);
			ans += val;
		}
	}

	cout << ans << '\n';

	return 0;
}

프림 알고리즘

프림 알고리즘의 시간 복잡도는 O(E log V)

#include <bits/stdc++.h>
using namespace std;

bool ch[10001];
struct Edge {
	int e;
	int val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

vector<pair<int, int> > graph[10001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	priority_queue<Edge> Q;

	int i, n, m, a, b, c, res = 0;
	
	cin >> n >> m;

	for (i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		graph[a].push_back({b,c});
		graph[b].push_back({ a,c });
	}

	Q.push({ 1,0 });
	while (!Q.empty()) {
		Edge tmp = Q.top();
		Q.pop();
		int v = tmp.e;
		int cost = tmp.val;

		if (ch[v] == 0) {
			res += cost;
			ch[v] = 1;
			for (i = 0; i < graph[v].size(); i++) {
				Q.push({ graph[v][i].first, graph[v][i].second });
			}
		}
	}

	cout << res << '\n';
}