[BOJ] 1647 도시 분할 계획

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

1647번: 도시 분할 계획

 

알고리즘: MST (Kruskal)

 

시간복잡도: O(MlogM)

 

---

접근:

1. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다.

2. 그 경로의 합은 최소가 되야 한다.

3. 분리된 마을은 2개

 

-> 1, 2번 조건을 통해 이 문제는 MST의 변형 문제라는 것을 알 수 있다.

    다만 기존 MST 문제와 차이점은 두 마을로 만들어야 한다는 것이다. (두개의 트리)

 

MST의 원리만 알면 간단한 문제다.

우선은 MST 알고리즘으로 하나의 마을을 만든 후,

가장 큰 가중치를 가진 선분을 제거해주면 자연스럽게 두 개의 마을로 쪼개진다.

 

// 1647: 도시 분할 계획

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;

struct e
{
	int a, b, c;	
};

bool cmp(const e &x, const e &y)
{
	return x.c < y.c;
}

int N, M, sum, maxC;
vector<int> p, r;

int findParent(int s)
{
	if (p[s] == s) return s;
	else 
		return p[s] = findParent(p[s]);
}

bool unionSet(int u, int v)
{
	u = findParent(u);
	v = findParent(v);
	
	if (u == v) return 0;
	
	if (r[u] < r[v])
		swap(u, v);
	
	p[v] = u;
	
	if (r[u] == r[v])
		++r[u];	
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> M;
	
	vector<e> G(M);
	
	for (int i = 0; i < M; ++i)
		cin >> G[i].a >> G[i].b >> G[i].c;
	sort(G.begin(), G.end(), cmp);
	
	for (int i = 0; i <= N; ++i)
	{
		p.push_back(i);
		r.push_back(0);
	}
	for (e i : G)
	{
		if(unionSet(i.a, i.b))
		{
			sum += i.c;
			maxC = MAX(maxC, i.c);
		}
	}
	
	cout << sum-maxC;	// 가장 큰 가중치를 가진 선분 제거
	return 0;
}