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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD 

SW Expert Academy

 

문제 요약

주어진 섬들의 좌표로 가중치를 구하고, 가중치를 가지고 MST 구하기

 

입력

첫째줄의 테스트 케이스의 수 T가 주어진다. 

 

이후 각 테스트 케이스의 첫 줄에는 섬의 개수 N이 주어지고 (1≤N≤1,000),

두 번째 줄에는 각 섬들의 정수인 X좌표, 세 번째 줄에는 각 섬들의 정수인 Y좌표가 주어진다 (0≤X≤1,000,000, 0≤Y≤1,000,000).

마지막으로, 해저터널 건설의 환경 부담 세율 실수 E가 주어진다 (0≤E≤1).

출력

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다.

같은 줄에 빈칸을 하나 두고, 주어진 입력에서 모든 섬들을 잇는 최소 환경 부담금을 소수 첫째 자리에서 반올림하여 정수 형태로 출력하라.

 

접근법

• N이 1000개이므로 O(N^2)로도 충분히 통과할 수 있다. N개의 점에 대해서 N-1개의 간선에 대한 가중치를 구하고, 해당 가중치를 벡터에 저장하고 정렬한다.
• 해당 가중치를 가지고 MST를 구하면 된다. 방법은 다양한데 나는 구현하기 쉬운 크루스칼 알고리즘을 썼다.
• 이후 구한 MST에 세율 E를 곱하고, 첫째 자리에서 반올림해서 정수 형태로 출력하면 되므로 구한 값에 round() 사용

시간 복잡도

가중치를 구하는데 O(N^2)만큼 소요되고, 구한 가중치를 정렬하는데 O(ElogE)만큼 소요된다. 이후 크루스칼 알고리즘은 N-1개의 간선을 구하면 종료되고, 최악의 경우 O(E)라고 생각했다. (마지막 간선을 선택하고 종료하는 경우)

E가 100만이므로 총 연산 횟수가 1000만번 이하이다.

이 문제는 20개를 합쳐 약 10초, 1개당 약 0.5초정도면 통과하므로 충분히 통과한다고 생각했다.

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <math.h>
using namespace std;
#define ll long long
constexpr int VMAX = 1002, EMAX = 1000002;
constexpr long long int INF = LLONG_MAX;
typedef struct Edge
{
    ll u, v, w;
    Edge() : Edge(-1, -1, INF) {} // 생성자 1
    Edge(ll uu, ll vv, ll ww) { u = uu, v = vv, w = ww; } // 생성자 2
    bool operator <(Edge& O) { return w < O.w; }
}Edge; 
ll v;
ll p[VMAX], r[VMAX], c[VMAX];
double cost;
Edge e[EMAX];
int find(int a)
{
    if (p[a] < 0) return a;
    return p[a] = find(p[a]);
}
bool merge(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b) return false;
    p[b] = a;
    return true;
}
void init()
{
    cin >> v;
    fill(r, r + VMAX, 0);
    fill(c, c + VMAX, 0);
    fill(p, p + VMAX, -1);
    for (int i = 0; i < v; i++)
        cin >> r[i];
    for (int i = 0; i < v; i++)
        cin >> c[i];
    cin >> cost;
    int cnt = 0;
    for (int i = 0; i < v; i++)
    {
        for (int j = 0; j < v; j++)
        {
            if (i == j) continue;
            e[cnt++] = Edge(i, j, ((abs(r[i] - r[j]) * abs(r[i] - r[j])) + ((abs(c[i] - c[j]) * abs(c[i] - c[j])))));
 
        }
    }
 
    sort(e, e + EMAX);
}
ll solve()
{
 
    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < EMAX; i++)
    {
        if (merge(e[i].u, e[i].v))
        {
            res += e[i].w;
            cnt++;
        }
        if (cnt == v - 1)
        {
            
            return round(res * cost);
        }
    }
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        init();
        cout << '#' << i << ' ' << solve() << "\n";
    }
    return 0;
}

 

몇 년 전에 자료구조 처음 공부할 때 MST랑 프림,크루스칼등을 배우고 유니온파인드를 배우고 넘어갔었는데, 그 당시에는 어렵다고 생각했는데 지금 다시 풀어보니까 생각보다 꽤 할만하다고 느꼈다. 

+ 라이님의 블로그를 많이 참고했다.

https://blog.naver.com/kks227/220799105543

최소 스패닝 트리(Minimum Spanning Tree) (수정: 2019-01-29)