백준 1197 최소 스패닝 트리 C++

문제

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

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

입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

풀이

최소 스패닝 트리(Minimum Spanning Tree, MST)는 주어진 그래프의 모든 정점들을 연결하는 그래프 중에서 그 가중치의 합이 최소인 트리이다.

MST의 특징: 사이클이 존재하지 않는다.  n개의 정점에 n-1개의 간선만 사용한다. 간선의 가중치의 합이 최소이다.

MST의 구현 방법에는 Kruskal 알고리즘과 Prim 알고리즘이 존재한다.

이 문제에서는 Kruskal 알고리즘을 통해 구해본다.

Kruskal 알고리즘은 그리디 알고리즘의 일종이다.

 

Kruskal 알고리즘의 작동 과정

1. 간선들의 가중치를 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 오름차순으로 선택 여부를 결정한다.

     사이클을 형성하지 않는 간선의 경우 선택한다.
     사이클을 형성하는 간선을 제외한다.
3. 해당 간선을 현재의 최소 비용 신장 트리(MST)에 추가한다.

4. 모든 정점을 연결될 때까지 위의 과정이 반복된다.

 

Kruskal 알고리즘의 시간복잡도: O(ElogV)

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int parent[10001];

struct edge {
	int u, v, w;

	edge(int u, int v, int w) {
		this->u = u;
		this->v = v;
		this->w = w;
	}
};

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

void merge(int u, int v) {
	u = find(u);
	v = find(v);

	parent[v] = u;
}

int compare_comp(const edge& a, const edge& b) {
	return a.w < b.w;
}

int main(void) {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	cout.tie(0);

	//1197번: 최소 스패닝 트리(MST) 구하기
	//Kruskal Algorithm 이용하기
	vector<edge> v;
	int V, E;
	long long ans = 0;
	cin >> V >> E;
	int A, B, C;

	for (int i = 1; i <= V; i++)
		parent[i] = i;

	for (int i = 0; i < E; i++) {
		cin >> A >> B >> C;
		v.push_back(edge(A, B, C));
	}

	sort(v.begin(), v.end(), compare_comp);

	for (auto n : v) {
		if (find(n.v) != find(n.u)) {
			merge(n.u, n.v);
			ans += n.w;
		}
	}

	cout << ans;
	return 0;
}