백준 BOJ 1774 - 우주신과의 교감

오늘의 USACO(5)

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

1774번: 우주신과의 교감

MST = 최소 스패닝 트리를 구하는 문제.

N개의 정점을 N-1개의 간선만을 사용해서 가장 가중치가 적게 연결해내면 된다.

 

나는 크루스칼 알고리즘을 사용해서 문제를 해결했다.

크루스칼 알고리즘의 구현에 있어서 연결되었는지 연결되지 않았는지를 판별하는데

유니온 파인드 자료구조를 사용하니까

이 역시 미리 배워둬야 문제를 해결할 수 있다.

 

좌표쌍만 주어지고 그래프를 연결하는 간선을 입력으로 주지 않는데,

NC2개의 모든 연결 가능한 경우에 대해서 직접 두 정점간의 거리를

피타고라스 정리를 활용해서 계산해준 다음 거리를 가중치로 가지는 간선을 만들어주면 된다.

 

가중치의 계산 과정에서

int범위를 넘어가기 때문에, 좌표는 long long 형으로 관리해주도록 하자.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<pair<double,pair<int,int>>> v;
int N,M,x,y;

int parent[1234] = {0};
pair<int,int> arr[1234];

double dist(pair<int,int> A, pair<int,int> B){
	long long x = (A.x-B.x);
	long long y = (A.y-B.y);
	return sqrt(x*x + y*y);
}

int find(int k){
	if(parent[k] == k) return k;
	return parent[k] = find(parent[k]);
}

void joint(int a, int b){
	a = find(a);
	b = find(b);
	if(a != b) parent[a] = b;
	return;
}

int main(){
	cout.precision(2);
	cout << fixed;
	
	for(int i=0; i<1234; i++) parent[i] = i;
	
	cin >> N >> M;
	for(int i=1; i<=N; i++){
		cin >> arr[i].x >> arr[i].y;
	}
	
	for(int i=1; i<=N; i++){
		for(int j=i+1; j<=N; j++){
			v.push_back({dist(arr[i],arr[j]),{i,j}});
		}
	}
	sort(v.begin(), v.end());
	
	for(int i=0; i<M; i++){
		cin >> x >> y;
		joint(x,y);
	}
	
	double ans = 0;
	int cnt = 1;
	for(auto node : v){
		int A = node.y.x;
		int B = node.y.y;
		
		if(find(A) != find(B)){
			joint(A,B);
			ans += node.x;	
		}
	}
	
	cout << ans;
	return 0;
}

범위를 넘어가는 int값에 대한 처리를 안해서

억까를좀당했다 ㅠㅠ