[BOJ] 네트워크 연결

[문제]

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

1922번: 네트워크 연결

[풀이]

1922

맞았습니다!!

4424

36

C++14 / 수정

1760

26초 전

 

1) 최소신장트리(MST) 사용 (그리디 탐색 방법 사용)

 

2) 비용을 기준으로 오름차순 정렬 

 

3) union_find를 사용해서 부모가 같지 않는 요소들을 합해가면서 최소 신장 트리를 완성한다. 

 

4) same_parent는 부모가 같은가 아닌가를 판단한다. 트리이기 때문에 사이클이 형성되지 않기 위해 검사한다. 

 

5) 비용 누적합을 출력

 

---

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//네트워크 연결 
//최소신장트리 사용 -크루스칼 -그리디 탐색 알고리즘 
typedef pair<int, int> pp;
typedef pair<int, pp> ppp;
 
vector<ppp> connect;
int parent[1001];
 
//////////union-find/////////
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
}
 
int find(int a) {
    if (parent[a ] == a) return a;
 
    return parent[a ] = find(parent[a]); //부모의 부모를 찾아 떠난다. 
}
 
void union_find(int a, int b) {
    int roota = find(a);
    int rootb = find(b);
 
    parent[roota] = rootb; //부모끼리 연결해줌 
}
//////////union-find/////////
bool same_parent(int a, int b) {
    //mst에서는 트리이기 때문에 사이클이 형성되면 안된다. -> 같은 부모를 가지고 있는지 확인해야한다. 
    int roota = find(a);
    int rootb = find(b);
 
    if (roota == rootb) return true;
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
 
    cin >> n >> m;
    //컴퓨터 수, 연결선 수 
 
    for (int i = 0; i < m; i++) {
        int a,b,fee;
 
        cin >> a >> b >> fee;
 
        connect.push_back(ppp(fee, pp(a,b )));
 
    }
    //input
 
    init(n);
 
    sort(connect.begin(), connect.end()); 
    //최소 신장 스패닝 트리는 간선의 가중치가 작은 것부터 탐색을 시작한다. 
    //비용을 기준으로 정렬한다. 
 
    int ans = 0;
    for (int i = 0; i < connect.size(); i++) {
        if (!same_parent(connect.at(i).second.first, connect.at(i).second.second)) {
            //같은 부모를 갖지 않아야 한다. 
            ans += connect.at(i).first;//비용 합산 
            union_find(connect.at(i).second.first,connect.at(i).second.second ); //트리에 더해준다. 
 
        }
    }
 
    cout << ans << '\n';
    return 0;
}