[백준] 21924번 - 도시 건설 (C++) 문제 및 풀이

문제) 백준 - 최소 스패닝 트리 - 도시 건설

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

21924번: 도시 건설

 

전형적인 최소 스패닝 트리 문제입니다. rank를 이용한 Disjointset과 kruskal 알고리즘을 이용하여 최소 비용을 구합니다. 비용의 개수로 모든 도시 연결 여부를 판단하여 -1 또는 절약 예산을 구합니다.

 

C++ 소스 코드)

	int kruskal() {
	int res = 0;
	sort(edges.begin(), edges.end());
	DisjointSet sets(N + 1);
	vector<int> costs;
	for (int i = 0; i < edges.size(); ++i) {
	int cost = edges[i].first;
	int u = edges[i].second.first; int v = edges[i].second.second;
	if (sets.find(u) == sets.find(v)) continue;
	sets.merge(u, v);
	costs.push_back(cost);
	res += cost;
	}
	if (costs.size() != N - 1)
	return -1;
	return res;
	}

view raw 21924.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2020000~/21924_%EB%8F%84%EC%8B%9C%20%EA%B1%B4%EC%84%A4.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions

 

 

PS) OverFlow를 조심합시다...