반응형

문제 출처 :


https://www.acmicpc.net/problem/4386



알고리즘 분석 :


문제 해결에 필요한 사항

1. 최소 스패닝 트리(MST) :: http://www.crocus.co.kr/733


이 문제는 최소 스패닝 트리를 기반으로 푸는 문제이다.


정점의 수가 100개 밖에 되지 않으니, 각각 입력받은 x,y 좌표에 대해 모든 간선을 생성시켜주고, x,y 좌표를 인덱스로 만들어준다.


그렇게 하면 결국 최소 스패닝 트리로 풀 수 있는 모양으로 바뀌게 된다.(from, to, val로)


푼 사람이 많이 없지만, 상당히 쉬운 문제이다.





소스 코드 : 


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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
typedef struct _INFO_
{
    double y;
    double x;
}INFO;
 
typedef struct _KS_
{
    int from;
    int to;
    double val;
}KS;
 
bool comp(const KS &a, const KS &b)
{
    return a.val < b.val;
}
 
typedef pair<double, int> pdi;
 
INFO info[101];
int parent[101];
vector<KS> graph;
 
double ans;
bool chk;
 
int find(int u)
{
    if (u == parent[u])
        return u;
 
    return parent[u] = find(parent[u]);
}
 
void merge(int u, int v)
{
    chk = false;
 
    u = find(u);
    v = find(v);
 
    if (u == v)
        return;
 
    parent[u] = v;
 
    chk = true;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        double y, x;
        scanf("%lf %lf", &y, &x);
        
        info[i].y = y;
        info[i].x = x;
 
        parent[i] = i;
    }
    
    // n이 100이니 모든 정점에 대해 간선을 계산하고
    // 위에서 구한 x,y 좌표를 인덱스화 하여 graph에 push해준다.
    int E = 0;
    for(int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
        {
            double y = abs(info[i].y - info[j].y);
            double x = abs(info[i].x - info[j].x);
 
            double len = sqrt(y*y + x*x);
 
            graph.push_back(KS{ i,j,len });
            E++; // 엣지 수 count
        }
 
    // 크루스칼 알고리즘을 위해 간선을 오름차순 정렬한다.
    sort(graph.begin(), graph.end(), comp);
    
    // 최소 스패닝 트리 제작
    for (int i = 0; i < E; i++)
    {
        merge(graph[i].from, graph[i].to);
 
        // merge를 성공하였을 때 가중치를 더한다.
        if (chk)
            ans += graph[i].val;
    }
    
    // 출력
    printf("%.2lf", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

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

[4485번] 녹색 옷 입은 애가 젤다지?  (2) 2017.04.07
[2934번] LRH 식물  (0) 2017.04.07
[2211번] 네트워크 복구  (0) 2017.04.04
[2887번] 행성 터널  (0) 2017.04.04
[6497번] Dark roads  (6) 2017.04.04

티스토리툴바