[Baekjoon] 1922 - 네트워크 연결 (C++)

1. 문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

 

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

1922번: 네트워크 연결

 

2. 해결 아이디어

각 노드를 연결하는 비용이 최소가 되게 하는 최소비용을 구하는 최소 신장 트리 문제이다.

크루스칼 알고리즘 (+유니온 파인드)를 사용해 문제를 해결했다.

 

재밌는 점은 '최소 비용' 만 구하려면 따로 node 이차원배열을 만들지 않고도, 그냥 바로 크루스칼 알고리즘만을 사용해 cost의 합으로 minCost를 구할 수 있다는 것이다.

노드 간의 연결정보와 가중치만을 저장하는 relations[][] 배열을 만들어 weight 오름차순으로 정렬해 크루스칼 알고리즘을 적용했다.

 

+) 정렬시 함수를 따로 만들어 그걸로 정렬 기준을 설정해 줄 수 있는데, 다음과 같이 bool형으로 함수를 작성하고, sort() 메소드 안에 함수 이름만 세 번째 인자로 넣어 주면 된다.

// 함수 정의 -> bool형으로, relations는 이차원 배열이라 그 원소인 그냥 배열을 인자로 가짐.
// 부등호 방향 바꾸면 오름차순 정렬.
bool cmp(vector<int> e1, vector<int> e2) {
    return e1[2] < e2[2];
}

// sort시
sort(relations.begin(), relations.end(), cmp);

 

크루스칼 알고리즘 참고

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

유니온 파인드 참고

https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/ 

유니온 파인드(Union-Find)

 

3. 코드

point[] 는 유니온 파인드시 루트 노드를 저장하는 배열,

relations[][]는 노드간 연결 노드 인덱스와 가중치를 저장하는 배열이다.

 

find()함수는 현재 노드의 루트 노드 인덱스를 반환하고

unionFind()함수는 노드 v1이 v2와 연결되어 있는지를 판별해 준다.

cmp함수는 relations[][] 자료형에 따라 따로 만들어준 sort()메소드에 인자로 들어가는 함수이다. 배열의 요소 중 가중치를 key로 하여 가중치를 오름차순 정렬을 할 수 있게 해준다.

// Baekjoon No. 1922 네트워크 연결 - 220930 solved
// Time Complexity O(nlogn)
// #최소신장트리, 크루스칼, 유니온 파인드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(vector<int> e1, vector<int> e2);
int find(vector<int>& point, int v1);
int unionFind(vector<int>& point, int v1, int v2);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, minCost, v1, v2, weight, size;
    int i;
    cin >> n >> m;
    vector<vector<int>> relations;
    vector<int> point(n);
    for (i = 0; i < n; i++)
        point[i] = i;
    for (i = 0; i < m; i++) {
        cin >> v1 >> v2 >> weight;
        v1--; v2--;
        if(v1 != v2)    // a != b
            relations.push_back({ v1, v2, weight });
    }
    
    // solving
    minCost = 0;
    size = relations.size();
    sort(relations.begin(), relations.end(), cmp);
            
    for (i = 0; i < size; i++) {
        if (unionFind(point, relations[i][0], relations[i][1])) {
            minCost += relations[i][2];
        }
    }
    
    // output
    cout << minCost;
    return 0;
}

// {{idx1, idx2, w1}, {}, ...{}}
bool cmp(vector<int> e1, vector<int> e2) {
    return e1[2] < e2[2];
}
int find(vector<int>& point, int v1) {
    if (point[v1] != v1)
        return find(point, point[v1]);
    return v1;
}
int unionFind(vector<int>& point, int v1, int v2) {
    int rootA = find(point, v1);
    int rootB = find(point, v2);
    if (rootA == rootB)
        return 0;
    else if (rootA > rootB) // point!
        point[rootA] = rootB;
    else
        point[rootB] = rootA;
    return 1;
}

4. 배운 점

유니온 파인드를 사용할 때 루트 노드를 저장하는 배열을 따로 만들었어야 했는데, 루트 노드를 저장하는 배열을 수정할 때, 현재 노드의 루트를 수정할게 아니라, 현재 노드의 루트 노드의 루트 노드를 수정해야 한다. (point라고 표시한 부분)