[백준] 1922번 네트워크 연결 (C++)

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

 

 

이 문제는 N개의 컴퓨터 개수가 주어지고 M개의 컴퓨터와 연결된 선, 비용이 주어진다.

이때 최소한의 비용을 사용하여 모든 N개의 컴퓨터가 연결되어야 한다.

 

따라서 문제를 읽어보면 최소신장트리를 구현하는 문제인걸 바로 알아챌 수 있다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M;
int unf[1001];
vector<tuple<int, int, int>> v;

int Find(int a) {
    if(a == unf[a]) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a < b) unf[a] = b;
    else unf[b] = a;
}

bool isUnion(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a != b) return false;
    return true;
}

void solve() {
    sort(v.begin(), v.end());

    int answer = 0;

    for(auto it : v) {
        auto [cost, Node1, Node2] = it;

        if(!isUnion(Node1, Node2)) {
            answer += cost;
            Union(Node1, Node2);
        }
    }

    cout << answer;
}

void Init() {
    for(int i = 1; i <= N; i++) {
        unf[i] = i;
    }
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({c, a, b});
    }

    Init();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

solve함수를 살펴보자

void solve() {
    sort(v.begin(), v.end());

    int answer = 0;

    for(auto it : v) {
        auto [cost, Node1, Node2] = it;

        if(!isUnion(Node1, Node2)) {
            answer += cost;
            Union(Node1, Node2);
        }
    }

    cout << answer;
}

 

먼저 입력된 간선을 비용을 기준으로 오름차순으로 정렬한다.

 

이후 배열을 순회하면서 1번 노드와 2번노드가 연결이 되어 있으면 합치지 않고

연결되지 않았으면 합쳐서 비용을 따로 계산해 준다.