1251. [S/W 문제해결 응용] 4일차 - 하나로

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE

SW Expert Academy

 

크루스칼 알고리즘으로 간단히 풀었음.

출력 형식 맞추느라 좀 애먹음. 

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;


struct Node {
	int y;
	int x;
};

struct Dis {
	int start;
	int end;
	double cost;

	bool operator<(const Dis& d)
	const{
		return cost > d.cost;
	}
};

int N;
Node arr[1000];
double odd;
long long result;
int parent[1000];

int findparent(int num)
{
	if (num == parent[num])
	{
		return num;
	}
	return num = findparent(parent[num]);
}

void merge(int a, int b)
{
	int node1 = findparent(a);
	int node2 = findparent(b);
	parent[node2] = node1;
}


int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			int x;
			cin >> arr[i].x;
			parent[i] = i;
		}

		for (int i = 0; i < N; i++)
		{
			int y;
			cin >> arr[i].y;
		}
		cin >> odd;

		priority_queue<Dis> pr;

		for (int i = 0; i < N; i++)
		{
			for (int j = i+1; j < N; j++)
			{
				double cost = sqrt(pow(abs(arr[i].x - arr[j].x), 2) + pow(abs(arr[i].y - arr[j].y), 2));
				pr.push({ i, j, cost });
			}
		}

		double result = 0;

		while (!pr.empty())
		{
			if (findparent(pr.top().start) != findparent(pr.top().end))
			{
				merge(pr.top().start, pr.top().end);
				result +=  odd * pow(pr.top().cost,2);
			}
			pr.pop();
		}

		cout << "#" << test_case <<" " <<round(result) << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}