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

문제 URL : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

문제 접근법 : 

MST 문제입니다.

크루스칼 알고리즘을 이용해서 풀었고 모든 간선을 만들어서 그비용을 최소로 만드는 문제입니다.

어렵지 않은 문제인데  문제조건에 정수만 나올수 있도록 소수점 안나오게 반올림 잘하셔야하구

형변환 잘하셔야 합니다. 몇번 틀려서 PYTHON이 거의 무한대의 범위를 제공할까 싶어서 똑같이했는데도

안되서 C++로 까다롭게 형변환만 잘맞추더니 답이맞더군요

 

소스코드 : 

#include<bits/stdc++.h>
using namespace std;

#define ll long long
vector<ll>x,y;
vector<tuple<ll,ll,ll>>v;
vector<int> parent;
int n;
double e;
void input(){
    cin>>n;
    x=y=vector<ll>(n);
    for(int i=0;i<n;i++)cin>>x[i];
    for(int i=0;i<n;i++)cin>>y[i];
    cin>>e;
}
int find(int idx){
    if(idx==parent[idx])return idx;
    return parent[idx]=find(parent[idx]);
}
bool merge(int a,int b){
    a =find(a);
    b =find(b);
    if(a==b)return false;
    parent[b]=a;
    return true;
}
void solve(){
    v.clear();
    parent = vector<int>(n);
    for(int i=0;i<n;i++)parent[i]=i;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            v.push_back({(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]),i,j});
        }
    }
    sort(v.begin(),v.end());
    double sum=0;
    for(auto[cost,node1,node2]:v){
        
        if(merge(node1,node2))
            sum+=cost;
    }
    cout<<(ll)round(sum*e)<<"\n";
}
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    int test;
    cin>>test;
    for(int i=1;i<=test;i++){
        cout<<"#"<<i<<" ";
        input();
        solve(); 
    }
}