[ SWEA 1251 ] 하나로 (C++)

Software ExpertAcademy의 하나로(1251) 문제이다.

[ 문제풀이 ]

1) 주어진 해저터널을 연결하는데, 이 때 환경 부담금을 최소로 하여 지불할 수 있도록 해저터널을 만들어야 하는 문제이다.

   즉, Minimal Spanning Tree를 만들어야 하는 문제이다.

   MST를 만들기 위해서 크루스칼 알고리즘으로 문제를 접근한다면 쉽게 해결할 수 있다.

   크루스칼 알고리즘에 대해서 잘 모른다면 아래의 링크를 타고 글을 읽고 오자 !

   [ 크루스칼 알고리즘에 대해서 알아보기(Click) ]

  본격적으로 문제를 풀어보자. 크루스칼 알고리즘을 써먹기 위해서는 먼저 가중치들을 모두 구한 후, 그 가중치들을 오름차순으로

  정렬을 해줘야 한다.

  그렇다면, 먼저 가중치를 구하는 법부터 알아보자. 이 문제에서 가중치는 '환경부담금'이 될 것이다.

  환경부담금은 문제에서 "환경부담세율과 각 해저터널 길이의 제곱의 곱"이라고 하였다.

  A(0, 100) 과 B(0, 0), 환경부담세율 E = 1 이라고 가정해보면, A와 B를 연결하는 해저터널을 만들 때 환경부담금을 구해보자.

  먼저, 해저터널 길이는 루트( (0 - 0)^2 + (100 - 0)^2 ) 이 될 것이고, 여기에 제곱한 값은 (0 - 0)^2 + (100 - 0)^2 이 될 것이다.

  이 값 곱하기 환경부담세율인 1을 곱한값이 환경부담금이 된다.

  이렇게, 만들 수 있는 모든 해저터널의 환경부담금을 구해서, 벡터에 저장해주자 !

 

  이후 과정은, 크루스칼 알고리즘을 그대로 적용하면 된다. 위의 크루스칼에 대한 글을 읽고 왔다면 어렵지 않게 구현할 수

  있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
 
typedef long long ll;
 
#define endl "\n"
#define MAX 1000 + 1
using namespace std;
 
typedef struct
{
    ll x;
    ll y;
}Pos;
 
ll N;
ll Answer;
ll Parent[MAX];
 
double E;
Pos P[MAX];
vector<pair<ll, pair<ll, ll>>> Edge;
 
void Initialize()
{
    memset(Parent, 0, sizeof(Parent));
    N = Answer = 0;
    E = 0.0;
    Edge.clear();
    for (int i = 0; i < MAX; i++)
    {
        P[i].x = -1;
        P[i].y = -1;
    }
}
 
ll Calc_Dist(int i, int j)
{
    ll dx = (P[i].x - P[j].x) * (P[i].x - P[j].x);
    ll dy = (P[i].y - P[j].y) * (P[i].y - P[j].y);
 
    return dx + dy;
}
 
void Input()
{
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        ll a; cin >> a;
        P[i].x = a;
    }
    for (int i = 1; i <= N; i++)
    {
        ll a; cin >> a;
        P[i].y = a;
    }
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = i + 1; j <= N; j++)
        {
            ll Dist = Calc_Dist(i, j);
            Edge.push_back(make_pair(Dist, make_pair(i, j)));
        }
    }
    cin >> E;
}
 
int Find(int x)
{
    if (Parent[x] == x) return x;
    else return Parent[x] = Find(Parent[x]);
}
 
bool SameParent(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x != y) return false;
    else return true;
}
 
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x != y) Parent[y] = x;
}
 
void Solution()
{
    sort(Edge.begin(), Edge.end());
 
    for (int i = 1; i <= N; i++) Parent[i] = i;
 
    for (int i = 0; i < Edge.size(); i++)
    {
        if (SameParent(Edge[i].second.first, Edge[i].second.second) == false)
        {
            Union(Edge[i].second.first, Edge[i].second.second);
            Answer = Answer + Edge[i].first;
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << (double)(Answer * E) << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed;
    cout.precision(0);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}