반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 최소 스패닝 트리

2. union find


최소 스패닝 트리를 형성한다.


아래 알고리즘은 크루스칼 알고리즘을 이용하여 문제를 해결하였다.






소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
struct info {
    int from, to;
    ll val;
};
 
vector<int> parent;
 
ll getDist(pll a, pll b) {
    return ((a.first - b.first) * (a.first - b.first)) + ((a.second - b.second) * (a.second - b.second));
}
 
bool comp(const info &a, const info &b) {
    if (a.val == b.val) {
        if (a.from == b.from)
            return a.to < b.to;
        return a.from < b.from;
    }
    return a.val < b.val;
}
 
int find(int a) {
    if (a == parent[a])
        return a;
 
    return parent[a] = find(parent[a]);
}
bool merge(int a, int b) {
    a = find(a);
    b = find(b);
 
    if (a == b)
        return false;
 
    parent[b] = a;
    return true;
}
int main() {
    freopen("input.txt""r", stdin);
    int tCase;
    scanf("%d"&tCase);
    for (int tc = 1; tc <= tCase; tc++) {
        int n;
        scanf("%d"&n);
 
        vector<pll> pt(n);
        vector<info> vc;
 
        parent.clear();
        for (int i = 0; i < n; i++)
            parent.push_back(i);
        
        for (int i = 0; i < n; i++)
            scanf("%d"&pt[i].first);
        for (int i = 0; i < n; i++)
            scanf("%d"&pt[i].second);
        double tax;
        scanf("%lf"&tax);
 
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                vc.push_back({ i,j,getDist(pt[i], pt[j]) });
 
        sort(vc.begin(), vc.end(), comp);
        
        ll ans = 0;
        for (int i = 0; i < vc.size(); i++) {
            int from = vc[i].from;
            int to = vc[i].to;
            ll val = vc[i].val;
            if (merge(from, to)) 
                ans += val;
        }
 
        printf("#%d %lld\n", tc, (ll)(ans * tax + 0.5));
    }
 
    return 0;
}
 
cs


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[17254번] 키보드 이벤트  (0) 2019.08.10
[SwExpertAcademy] 줄세우기  (0) 2019.08.07
[4803번] 트리  (4) 2019.08.03
[1245번] 균형점  (0) 2019.07.31
[1258번] 행렬찾기  (0) 2019.07.30