×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,191,227명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


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
[3124번] 최소 스패닝 트리  (0) 2019.07.01
[1247번] 최적 경로  (0) 2019.06.27
[1263번] 사람 네트워크2  (0) 2019.06.20
[11060번] 점프 점프  (0) 2019.06.15