[Baekjoon/C++] 1197번 - 최소 스패닝 트리 (크루스칼 알고리즘)

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

 

입력

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

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

 

출력

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

 

---

 

 풀이

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

struct Edge {
    int start = 0;
    int end = 0;
    int weight = 0;
};

int V, E;
int parent[10001];
vector<Edge> edge;

bool compare(Edge a, Edge b);
int findParent(int n);
int mst();

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

// 루트 노드 찾기
int findParent(int n) {
    if (parent[n] == 0) return n;

    return parent[n] = findParent(parent[n]);
}

// 최소 스패닝 트리
int mst() {
    int result = 0;

    for (int i = 0; i < E; i++) {
    	// 선택한 간선의 두 노드의 루트 노드 찾기
        int a = findParent(edge[i].start);
        int b = findParent(edge[i].end);

        // 두 노드의 루트 노드가 같지 않다면 서로 연결한다.
        if (a != b) {
            parent[b] = a;
            result += edge[i].weight;
        }
    }

    return result;
}

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

    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        edge.push_back({ a, b, c });
    }

    sort(edge.begin(), edge.end(), compare);

    cout << mst() << '\n';

    return 0;
}

크루스칼 알고리즘

 최소 스패닝 트리를 만들 때 사용하는 알고리즘으로, O(ElogV)의 시간 복잡도를 가진다. 크루스칼 알고리즘은 아래의 순서를 따라 작동한다.

 

1. 가장 작은 가중치를 가지고 있는 간선을 선택한다.

2. 선택한 간선의 두 노드의 루트 노드가 서로 같은지 확인한다.

3-1. 두 노드의 루트 노드가 다르다면 선택한 간선을 연결한다. 

3-2. 두 노드의 루트 노드가 같다면 선택한 간선을 연결하면 사이클이 발생하므로 연결하지 않는다.

 

// 최소 스패닝 트리
int mst() {
    int result = 0;

    for (int i = 0; i < E; i++) {
    	// 선택한 간선의 두 노드의 루트 노드 찾기
        int a = findParent(edge[i].start);
        int b = findParent(edge[i].end);

        // 두 노드의 루트 노드가 같지 않다면 서로 연결한다.
        if (a != b) {
            parent[b] = a;
            result += edge[i].weight;
        }
    }

    return result;
}

 크루스칼 알고리즘으로 구현한 최소 스패닝 트리를 만드는 함수이다.

 

 

<참고>

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전