백준 1922

ALGORITHM
2025-09-20

네트워크 연결

관련 개념

#최소 신장 트리 #크루스칼

문제

1922

📌 1 단계 : 문제 분석하기

  • 전형적인 MST 문제이다.
  • 이전에 다룬바가 있으니 자세한 설명은 생략.
  • 다만, C++로 유니온 파인드와 크루스칼의 알고리즘을 구현하는 방식만 잘 기억하자

📌 2 단계 : 손으로 풀어보기

📌 3 단계 : 슈도 코드 작성하기

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm> 
#include <set>
#include <tuple>
 
using namespace std;
 
class DisjointSet {
private:
	vector<int> parent;
public:
	DisjointSet(int N) {
 
		parent.resize(N + 1);
 
		for (int i = 1; i <= N; i++) {
			parent[i] = i;
		}
	}
 
	int find(int i) {
		if (parent[i] == i) {
			return i;
		}
 
		return parent[i] = find(parent[i]);
	}
 
	void unite(int i, int j) {
 
		int root_i = find(i);
		int root_j = find(j);
 
		parent[root_j] = root_i;
	}
 
};
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int N, M;
	int answer = 0;
 
	cin >> N >> M;
 
	DisjointSet union_find = DisjointSet(N);
 
	vector<tuple<int, int, int>> graph(M);
 
	for (int i = 0; i < M; i++) {
		int start, dest, weight;
		cin >> start >> dest >> weight;
		graph[i] = { start, dest, weight };
	}
 
	sort(graph.begin(), graph.end(), [](const auto& a, const auto& b) {
		return get<2>(a) < get<2>(b);
		});
 
	// 크루스칼 알고리즘 적용
	// 가중치의 합만 계산하면 됨
	for (auto& a : graph) {
 
		// 사이클이 있는지 확인 - 있는 경우
		if (union_find.find(get<0>(a)) == union_find.find(get<1>(a))) {
			continue;
		}
		else {
			answer += get<2>(a);
			union_find.unite(get<0>(a), get<1>(a));
		}
	}
 
	cout << answer;
 
	return 0;
}