[백준/C++] 1647번: 도시 분할 계획

문제

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

1647번: 도시 분할 계획

---

문제 요약

n개의 집과 m개의 길로 이루어져 있는 마을이 있다.

 

각 길에는 길을 유지하는데 드는 유지비가 있다.

 

마을에 길이 너무 많으므로, 길을 없애 유지비의 합을 최소로 하는 2개의 마을로 분할해야한다.

 

이에 발생하는 비용을 출력한다. 

---

코드

#include <iostream>
#include<algorithm>
#include<vector>
#include<tuple>
#include<queue>

#define MAX_N 100000

using namespace std;

vector<tuple<int, int, int>> v;

int uf[MAX_N + 1]; // uf[i]: i번 집이 속한 그룹 번호
int n, m;

// 집 x의 그룹번호 반환
int find(int x) {
	if (uf[x] == x) return x;
	uf[x] = find(uf[x]);
	return uf[x];
}

// 집 x와 집 y를 같은 그룹으로 만들기
void union_(int x, int y) {
	x = find(x);
	y = find(y);

	uf[x] = y;
}

int main() {
   
	cin >> n >> m;

	// uf 초기 설정 (각 집은 자신만의 그룹에 속해 있음)
	for (int i = 1; i <= n; i++) {
		uf[i] = i;
	}

	// v에 길 정보 저장
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;

		v.push_back({ w, a, b }); // {유지비, 집1, ,집2}
	}

	int res = 0;
	int max_w = 0;

	sort(v.begin(), v.end()); // 유지비가 적은 순으로 오름차순 정렬

	// 유지비가 작은 길부터 이어주기
	for (int i = 0; i < v.size(); i++) {
		int w, a, b;
		tie(w, a, b) = v[i];

		// 같은 그룹이라면 건너뛰기
		if (find(a) == find(b)) continue;

		union_(a, b);
		res += w;
		max_w = max(max_w, w); 
	}

	// 가장 큰 유지 비용을 갖는 길을 제거하여 그룹을 2개로 분할
	cout << res - max_w;

}

---

코드 설명

유니온 파인드를 이용한 크루스칼 알고리즘을 이용하여 문제를 해결한다.

 

단, 마을을 2개로 분할해야 하기 때문에 먼저 최소 비용으로 하나의 마을을 만들고, 마지막에 가장 유지비가 많이 드는 길 하나를 없앤다.