반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 크루스칼 알고리즘

2. Union Find




크루스칼 알고리즘을 이용하는 기본적인 문제이다.


하지만 mergeSort를 이용하려 하니 스택 메모리가 1MB밖에 되지 않아 런타임 에러가 발생한다.


어쩔수없이 이부분에 대해서는 STL을 사용하여 해결하였다.







소스 코드 : 


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
#include <iostream>
#include <algorithm>
using namespace std;
 
struct KRUSCAL {
    int from, to, val;
};
 
KRUSCAL ks[100002];
KRUSCAL tmp[100002];
int ksIdx;
 
int parent[100002];
 
bool comp(const KRUSCAL &a, const KRUSCAL &b) {
    return a.val < b.val;
}
//void mergeSort(int s, int e) {
//    if (s < e) {
//        int m = (s + e) / 2;
//        mergeSort(s, m);
//        mergeSort(m + 1, e);
//
//        int left = s, right = m + 1;
//        int idx = s;
//
//        while (left <= m || right <= e) {
//            if (right > e || (left <= m && ks[left].val < ks[right].val))
//                tmp[idx++] = ks[left++];
//            
//            else
//                tmp[idx++] = ks[right++];
//        }
//
//        for (int i = s; i <= e; i++)
//            ks[i] = tmp[i];
//    }
//}
 
int find(int u) {
    if (u == parent[u])
        return u;
 
    return parent[u] = find(parent[u]);
}
 
bool merge(int u, int v) {
    u = find(u);
    v = find(v);
 
    if (u == v)
        return false;
 
    parent[u] = v;
    return true;
}
int main() {
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        for (int i = 0; i < 100002; i++)
            parent[i] = i;
 
        int v, e;               
        scanf("%d %d", &v, &e);
 
        for(int i = 0; i < e; i++) {
            int from, to, val;
            scanf("%d %d %d", &from, &to, &val);
 
            ks[i] = { from, to, val };
        }
        
        sort(ks, ks + e, comp);
        //mergeSort(0, e - 1);
        
        long long ans = 0;
        for (int i = 0; i < e; i++)
            if (merge(ks[i].from, ks[i].to)) 
                ans += ks[i].val;
 
        printf("#%d %lld\n", tc, ans);
    }
 
    return 0;
}
 
cs



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

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

[1266번] 소수 완제품 확률  (0) 2019.07.03
[1269번] 대칭 차집합  (0) 2019.07.02
[1247번] 최적 경로  (0) 2019.06.27
[1263번] 사람 네트워크2  (0) 2019.06.20
[11060번] 점프 점프  (0) 2019.06.15

티스토리툴바