백준) 1197 최소 스패닝 트리

1197. 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1≤V≤10,000)와 간선의 개수 E(1≤E≤100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않는다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 

3 3
1 2 1
2 3 2
1 3 3

예제 출력 

3

1. 접근

대놓고 최소스패닝트리를 찾으라고 써있는 문제.

크루스칼 알고리즘을 쓰자.

2. 풀이

간선들을 가중치 순으로 정렬하자.

가장 작은 간선부터 보면서 추가시 사이클이 생기지 않는다면 추가해 준다.

사이클의 유무는 디스조인트-셋 으로 확인해준다. 루트 노드가 같다면 연결되어 있다는 뜻이고, 추가하면 사이클이 생겨버린다.

가중치의 합만 구하면 되므로, 간선의 순서를 기억하지 않아도 좋다.

다음을 참고 : http://js1jj2sk3.tistory.com/22

3. 코드

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int v, e, a, b, c, i, cnt, sum;
struct edge {
    int weight, from, to;
};
bool operator<(const edge& e1, const edge& e2) {
    return e1.weight < e2.weight;
}
edge E[100001];
 
int parent[100001];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void unite(int x, int y) {
    x = parent[x];
    y = parent[y];
    parent[x] = y;
}
 
int main() {
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; ++i) {
        scanf("%d %d %d", &a, &b, &c);
        E[i] = { c,a,b };
    }
    for (i = 1; i <= v; ++i)
        parent[i] = i;
    sort(E, E + e);
 
    i = 0;
    while (cnt != v - 1) {
        a = E[i].from;
        b = E[i].to;
        if (find(a) != find(b)) {
            unite(a, b);
            cnt++;
            sum += E[i].weight;
        }
        i++;
    }
    printf("%d", sum);
    return 0;
}

4

4. 후기

구조체를 algorithm : sort에 적용시키는 방법을 기억해두자. 연산자 오버로딩이 필요하다.