greentea31's Note

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

풀이 과정

컴퓨터와 각 컴퓨터를 연결하는 비용을 줄 테니, 모든 컴퓨터를 연결 상태 (모든 컴퓨터 사이의 경로가 존재해야 함)로 만드는데 필요한 최소 비용을 구하는 문제이다.

컴퓨터와 컴퓨터를 연결하는 비용을 방향이 없는 가중치 그래프로 모델링 하면, 문제에서 요구하는 것은 그래프의 최소 신장 트리를 만들라는 것임을 알 수 있다.

최소 신장 트리를 만드는 방법은 크루스칼 알고리즘, 프림 알고리즘 2가지 방법이 있고, 크루스칼 알고리즘을 이용하여 문제를 해결하였다.

간선을 가중치를 기준으로 오름차순으로 정렬하고, 간선의 출발 지점과 도착 지점이 이미 연결되어 있지 않으면 최소 신장 트리에 속하는 간선으로 추가하는 방법이다. 이미 연결되어 있는지 아닌지는 유니온-파인드 알고리즘을 사용하여 판단하였다.

https://greentea31.tistory.com/117

유니온-파인드는 위의 문제를 풀고 공부하면 무엇인지 알 수 있다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int parent[1001];

int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}

void uni(int a, int b) {
    int aRoot = parent[a];
    int bRoot = parent[b];
    if (aRoot == bRoot) return;
    parent[aRoot] = bRoot;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, a, b, c;
    int answer = 0;
    cin >> N >> M;

    tuple<int, int, int> edge[100005];

    for (int i = 1; i < N+1; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        edge[i] = make_tuple(c, a, b);
    }

    sort(edge, edge+M);

    for (int i = 0; i < M; i++) {
        tie(c, a, b) = edge[i];
        if (find(a) == find(b)) continue;
        uni(a, b);
        answer += c;
    }

    cout << answer;

    return 0;
}