boj, 백준) 1647. 도시 분할 계획 ( C / C++)

1. 문제 링크

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

1647번: 도시 분할 계획

2. 문제 개요

 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

 

마을을 2개로 쪼개고, 각 마을의 집들은 다 연결되어있어야 한다. 길의 최소비용을 구해보자.

 

3. 문제 힌트

 

(1) 마을1개에서 모든 집들을 가장적은 비용으로 연결하는 방법

(2) 어떤 간선을 하나 제거하면 마을 2개가 되고 최소비용이 될까?

 

4. 문제 풀기

우선 문제에서 주어진 조건을 만족하면서 모든 집들을 연결하는 방법은 MST를 구하는 것이다.

 

Kruskal알고리즘을 사용해서 구해볼 것이다. 구하기에 앞서 Union find (자료구조라고 해야 하나..)도 알아야 한다.

 

따라서 3번 힌트에서,

(1)은 Kruskal알고리즘을 사용해서 비용을 구하고,

(2)는 가장 비용이 큰 간선을 제거해야 각 마을에서 가장적은 비용으로 모든 집들을 연결할 수 있게 된다.

 

나는 MST를 찾고 간선 중 최댓값을 빼는 방식으로 했는데,

다른 분들은 n-2개의 edge만 찾아서 해결하는 방법도 있었다.

 

참고로 Kruskal 알고리즘은 비용을 기준으로 오름차순으로 정렬해야 하기 때문에 시간 복잡도는 정렬하는 시간에 영향을 받는다.

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct disjointset
{
	void init(int size){
		p.resize(size + 1);
		for (int i = 1; i <= size; ++i)
			p[i] = i;
	}

	int find(int x){
		if (p[x] == x)
			return x;
		return p[x] = find(p[x]);
	}

	//union x <- y
	void union_set(int x, int y) {

		x = find(x);
		y = find(y);

		if (x != y)
			p[y] = x;
	}
	vector<int> p;
}dset;

//cost,<from, to>
vector <pair<int, pair<int, int>>> v;
int n, m;
int cnt, ans;
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int cost, from, to;
		scanf("%d %d %d",&from, &to, &cost);
		v.push_back({ cost,{from,to} });
	}
	dset.init(n);
	sort(v.begin(), v.end());

	int val = -1;

	//모든 edge에 대하여
	for (int i = 0; i < m; ++i) 
	{
		if (cnt == n-1)	break;

		if (dset.find(v[i].second.first) != dset.find(v[i].second.second)) {
			dset.union_set(v[i].second.first, v[i].second.second);
			++cnt;
			val = max(val, v[i].first);
			ans += v[i].first;
		}
	}

	printf("%d", ans - val);
	

	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~