(백준 4386번 별자리 만들기) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)

백준 4386번

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

 

처음에는 스패닝 트리 문제라는 생각이 안 드는 문제..

 

n개의 별들을 잇는 최소의 거리를 찾는 문제다. n개의 별들 사이의 거리는 주어져 있지 않으므로 $\frac{n \times (n-1)}{2}$의 간선에 대해 길이를 먼저 구해야 한다. 이 중 거리가 최소인 간선부터 이어(일종의 그리디 알고리즘) 최소의 간선 갯수만 이으면 된다. V개의 노드가 있다면 V-1개의 간선을 잇는 것이 최소이기 때문에 자연스럽게 트리 모양이 된다는 것을 알 수 있다.

 

즉,  가중치의 합이 최소인 트리를 찾는 MST 문제가 되는 것이다!

 

참고로 double을 사용할 때 %lf를 쓴다는 사실과 소수점 두번째 자리까지만 프린트하는 %.2lf를 까먹어 구글링해보았다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef pair<double, double> P;

struct Edge {
	int u, v; double w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};

int uf[100];

int find(int a) {
	if (uf[a] < 0) return a;
	return uf[a] = find(uf[a]);
}

int merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[b] = a;
	return true;
}

int main() {
	int N; scanf("%d", &N);

	// 별이 1개인 경우 - 비용 = 0
	if (N == 1) {
		puts("0");
		return 0;
	}
	
	vector<P> Point(N);
	vector<Edge> v(N * (N-1) / 2);
	
	for (int i = 0; i < N; i++){
		double x, y; scanf("%lf %lf", &x, &y);
		Point[i] = { x, y };
	}
	int cnt = 0;
	for (int i = 0; i < N-1; i++) {
		for (int j = i + 1; j < N; j++) {
			double x_i = Point[i].first, y_i = Point[i].second;
			double x_j = Point[j].first, y_j = Point[j].second;
			double weight = sqrt(pow((x_i - x_j), 2) + pow((y_i - y_j), 2));
			v[cnt++] = { i, j, weight };
		}
	}

	sort(v.begin(), v.end());
	fill(uf, uf + N, -1);

	cnt = 0;
	double result = 0; 
	for (Edge& e: v){
		if (merge(e.u, e.v)) {
			result += e.w;
			if (++cnt == N - 1) break;
		}
	}

	printf("%.2lf", result);
	return 0;

	// cout 소수점 출력
	// cout << fixed;
	// cout.precision(2);
}

 

MST 문제는 Union Find 아이디어 자체가 쉽게 떠오르지 않기 때문에.. MST 문제인 걸 알고 푸는 순간 (MST를 찾는 알고리즘을 알고 있다면) 비교적 쉽게 풀리는 것 같다!