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

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

1197번: 최소 스패닝 트리

백준 1197번 최소 스패닝 트리를 풀었다.

 

스패닝 트리는 그래프 내의 모든 정점을 포함하는 트리다.
n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 스패닝 트리가 된다.

 

최소 스패닝 트리는 이러한 스패닝 트리 중에 간선의 가중치 합이 최소인 트리다.

최소 스패닝 트리를 푸는 알고리즘은 프림 알고리즘과 크루스칼 알고리즘이 있는데 나는 프림 알고리즘을 사용해서 풀어봤다.

 

https://yabmoons.tistory.com/362

알고리즘 동작 원리는 위의 블로그를 참고했다.

2중 for문을 사용해서 O(V^2) 시간이 걸리는 알고리즘와 최소 힙을 사용해서 O(E logV) 시간이 걸리는 알고리즘 두개를 사용해봤다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define INF	2147483647
typedef pair<int, int> node; // end, cost
struct compare {
	bool operator()(node a, node b) {
		return a.second > b.second;
	}
};
vector<node> vertex[10001];
vector<int> dist;
int selected[10001];
int visited[10001];

int v, e;
long long MST_cost;

void Prim() {
	for (int i = 1; i <= v; i++) {
		int cur = 0;
		int min_dist = INF;
		for (int j = 1; j <= v; j++) {
			if (selected[j] == 0 && min_dist > dist[j]) {
				min_dist = dist[j];
				cur = j;
			}
		}

		MST_cost += min_dist;
		selected[cur] = 1;

		for (int j = 0; j < vertex[cur].size(); j++) {
			int next = vertex[cur][j].first;
			int cost = vertex[cur][j].second;

			if (selected[next] == 0 && dist[next] > cost)
				dist[next] = cost;
		}
	}
}

void Prim_heap() {
	priority_queue<node, vector<node>, compare> pq;
	for (int i = 0; i <vertex[1].size(); i++) {
		int next = vertex[1][i].first;
		int cost = vertex[1][i].second;
		pq.push({ next,cost });
	}
	
	visited[1] = 1;
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = pq.top().second;
		pq.pop();

		if (visited[cur] == 0) {
			visited[cur] = 1;
			MST_cost += cost;
			for (int i = 0; i < vertex[cur].size(); i++) {
				int next = vertex[cur][i].first;
				int next_cost = vertex[cur][i].second;
				if (visited[next] == 0) {
					pq.push({ next,next_cost });
				}
			}
		}
	}
	

}

int main() {
	cin >> v >> e;
	for (int i = 0; i < e; i++) {
		int start, to, cost;
		scanf("%d %d %d", &start, &to, &cost);
		vertex[start].push_back({ to,cost });
		vertex[to].push_back({ start,cost });
	}

	dist.assign(v + 1, INF);
	dist[1] = 0;
	//Prim();
	Prim_heap();
	cout << MST_cost;

	return 0;
}