[백준] prim's algorithm, kruskal algorithm

4386 별자리 만들기.

 

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
int N; float w[101][101]; pair<float, float>p[101];

struct Edge {
	int a;
	int b;
	float w;
	bool operator<(const Edge& d) {
		return w > d.w;
	}
};
struct comp {
	bool operator()(Edge& f, Edge& d) {
		return f.w > d.w;
	}
};
float dist(int f, int t) {
	return sqrt(pow(p[f].first - p[t].first, 2) + pow(p[f].second - p[t].second, 2));
}
int inY[1001]; //it shows if a specific vertex is in Y
float sum = 0;
int main() {
	FAST;
	cin >> N;
	REP(i, N) {
		cin >> p[i].first >> p[i].second;
	}

	//let's use Prim's algorithm
	priority_queue<Edge, vector<Edge>, comp>Q;
	REP(i, N)REP(j, N) {
		if (i == j)w[i][j] = 0;
		if (w[i][j])continue;
		float d = dist(i, j);
		w[i][j] = d;
		w[j][i] = d;
	}
	int cur = 1; //let's start with 1
	inY[cur] = 1;
	vector<int>Y; //create an empty set
	Y.push_back(cur);
	while (Y.size() != N) {  //V-1 times

		REP(i, N) {//EXTRACT_MIN : find nearest vertex from Y in V-Y
			if (inY[i])continue; //if i is in Y continue;
			Q.push({ cur,i,w[cur][i] });
		}
		while (inY[Q.top().a] && inY[Q.top().b]) {
			Q.pop();
		}
		auto e = Q.top();
		Q.pop();

		inY[e.a] ? cur = e.b : cur = e.a;

		Y.push_back(cur);
		inY[cur] = 1;
		sum += e.w;

	}
	cout << sum;
}

왜 프림의알고리즘을 사용하는가 ?

모든 노드로부터 모든노드로의 간선이 존재하므로 간선의 수가 너무 많다. 따라서 노드 중심으로 그래프를 확장하는 프림의 알고리즘이 더 좋을것.