코딩 공부/백준

[백준][C++] 14621 나만 안되는 연애

김 정 환 2021. 3. 13. 14:30
반응형

www.acmicpc.net/problem/14621

 

14621번: 나만 안되는 연애

입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의

www.acmicpc.net

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    - 기본적인 크루스칼 알고리즘에 양쪽 노드가 다른 성별인지 확인해주는 조건만 걸어주면 된다.

        1. 노드의 성별을 저장할 배열을 생성한다.

        2. 사이클을 확인하는 부분에 다른 성별인지 확인하는 조건을 추가한다.

 

 

 

구현(C++)

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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<char> nodes;
vector<int> parents;
vector<pair<pair<intint>int> > edges;
 
 
bool cmp(pair<pair<intint>int> a, pair<pair<intint>int> b){
    return a.second < b.second;
}
 
 
int get_parent(int a){
    if(parents[a] == a) return a;
    else return parents[a] = get_parent(parents[a]);
}
 
 
bool is_cycle(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a == b) return true;
    else return false;
}
 
 
void union_parents(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a > b) parents[a] = b;
    else parents[b] = a;
}
 
 
bool is_diff(int a, int b){
    if(nodes[a] == nodes[b]) return false;
    else return true;
}
 
 
void kruskal(){
    
    for(int i=1; i<=n; i++) parents[i] = i;
    sort(edges.begin(), edges.end(), cmp);
 
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        
        // 사이클인지 확인 && 양쪽 노드가 다른 성별인지 확인
        if(!is_cycle(edges[i].first.first, edges[i].first.second) 
        && is_diff(edges[i].first.first, edges[i].first.second)){
            union_parents(edges[i].first.first, edges[i].first.second);
            sum += edges[i].second;
        }
    }
    
    // 모두 연결되었는지 확인 
    int p = parents[1];
    for(int i=1; i<=n; i++){
        if(get_parent(i) != p){
            cout << -1 << "\n";
            return;
        }
    }
    cout << sum << "\n";
}
 
int main(void){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin >> n >> m;
    
    nodes.resize(n+1);
    parents.resize(n+1);
    
    char c;
    for(int i=1; i<=n; i++){
        cin >> nodes[i];
    }
    
    int u,v,cost;
    for(int i=0; i<m; i++){
        cin >> u >> v >> cost;
        edges.push_back({{u, v}, cost});
    }
    
    kruskal();
    
    return 0;
}
cs

 

 

 

시행착오

반응형

'코딩 공부 > 백준' 카테고리의 다른 글

[백준][C++] 12764 싸지방에 간 준하  (0) 2021.03.15
[백준][C++] 13905 세부  (0) 2021.03.13
[백준][C++] 2931 가스관  (0) 2021.03.12
[백준][C++] 10993 별 찍기 - 18  (0) 2021.03.12
[백준][C++] 2665 미로만들기  (0) 2021.03.04