SWEA 1251 하나로 C++

문제: SW Expert Academy 1251 하나로

 

"섬이나 도시, 컴퓨터 등등 어떤 정점들을 모두 잇는 최소 경로가 필요하다!"라는 문제가 나오면 십중팔구 최소 신장 트리(MST) 문제이다.

 

이 문제 또한 크루스칼 알고리즘을 적용하여 MST를 생성해서 풀 수 있는 문제였다.

 

본 블로그에서 몇 번 설명을 진행한 풀이가 있는데, 크루스칼 알고리즘을 간단히 설명하면 다음과 같다.

 

1. 어떤 노드들을 잇는 간선들을, 그 비용을 기준으로 오름차순 정렬한다.

2. 가장 비용이 적은 간선부터 연결을 시작한다.

3. 이 때, 간선을 연결했을 때 싸이클이 발생하게 된다면 해당 간선은 연결하지 않고 건너 뛴다.

 

위 알고리즘 구현을 위해서는 간선 정보를 어떤 컨테이너에 잘 담고, 정렬할 수 있어야한다. 그리고 싸이클 발생 여부 확인을 위해서 Union-Find를 구현할 수 있어야 한다.

 

특이한 점 몇가지는, 노드 간의 거리나 간선 정보가 주어지지 않는다. 즉, 주어진 모든 섬들에 자유롭게 해양 터널을 설치할 수 있는 상황이므로 모든 섬 간의 거리를 미리 구하기만 하면 된다.

 

이 때 연산 시 오버플로우가 발생하지 않도록, 연산에 참여하는 모든 변수들을 long long으로 선언하였다.

 

그리고 소수점아래 첫째자리에서 반올림을 할 때, round 함수를 사용하지 않고 fixed와 precision을 이용하였다.

 

/* SWEA 1251 하나로 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
const int INF = 1e9;
int t, T, n, p[1001];
double e; // 세율
ll dist[1001][1001];
pair<ll, ll> islands[1001]; // 최대 1000개의 섬
vector<pair<pair<ll, ll>, ll>> edges;
 
void island_distance()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                dist[i][j] = 0;
            else
            {
                ll dx = islands[i].first - islands[j].first;
                ll dy = islands[i].second - islands[j].second;
                dist[i][j] = dx * dx + dy * dy;
            }
        }
    }
 
    for (int i = 1; i <= n; i++) // 중복 방지를 위해서 인접행렬 중 상부삼각행렬만 포함 
        for (int j = i + 1; j <= n; j++) // 섬 a에서 섬 a로 가는 간선은 고려할 필요 없음
            edges.push_back({ {i, j}, dist[i][j] });
}
 
// find
int find_parent(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find_parent(p[x]);
}
 
// union
void union_parent(int a, int b)
{
    a = find_parent(a);
    b = find_parent(b);
 
    if (a < b)
        p[b] = a;
    else
        p[a] = b;
}
 
bool cmp(pair<pair<int, int>, ll> p1, pair<pair<int, int>, ll> p2)
{
    return p1.second < p2.second;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cout << fixed;
    cout.precision(0);
 
    cin >> T;
    for (t = 1; t <= T; t++)
    {
        edges.clear(); // 간선 배열 초기화
 
        cin >> n;
        for (int i = 1; i <= n; i++) // x
            cin >> islands[i].first;
        for (int i = 1; i <= n; i++) // y
            cin >> islands[i].second;
 
        for (int i = 1; i <= n; i++) // 부모 배열 초기화
            p[i] = i;
 
        cin >> e;
 
        // 모든 섬-to-섬 거리 관계 파악
        island_distance();
 
        // 크루스칼 알고리즘
        sort(edges.begin(), edges.end(), cmp); // 간선 정보 오름차순 정렬
 
        double tot_fair = 0.; // 모든 섬을 연결하는데 필요한, 총 환경부담금
        for (const auto edge : edges)
        {
            int i1 = edge.first.first, i2 = edge.first.second; // i1과 i2를 연결하는 간선
            ll L2 = edge.second; // i1과 i2를 연결하는데 필요한 환경부담금
 
            if (find_parent(i1) == find_parent(i2)) // 싸이클 생성할 경우
                continue; // 해당 간선 무시
 
 
            union_parent(i1, i2); // 두 섬 연결 (같은 집합에 포함시킴)
            tot_fair += L2 * e;
        }
 
        cout << "#" << t << ' ' << tot_fair << endl;
    }
    
    return 0;
}