백준 1197 최소스패닝 트리 (프림, 크루스칼)

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 MST(minimun spanning tree)의 가중치를 구해서 출력하는 문제입니다.

 

기본적으로 MST를 구하는 방법은 prim 알고리즘과 kruskal 알고리즘이 있습니다. 저는 두가지 방법으로 모두 풀어봤습니다.

 

우선 kruskal 알고리즘은 가중치가 가장작은 간선부터 하나씩 이어나가며 모든 정점을 방문하는 방법입니다. 이때 주의할점은 사이클이 발생하게 된다면 그 간선은 건너뛰어야 합니다. 따라서 사이클 발생유무를 체크하기 위해서 kruskal 알고리즘은 유니온 파인드 구조를 사용합니다. 사이클이 생기지 않는 조건은 두 정점의 루트노드가 동일한 경우입니다. 

 

다음은 prim 알고리즘입니다. prim알고리즘은 정점을 기준으로 인접한 간선들중 가중치가 가장 작은 간선의 정점으로 이동하는 알고리즘 입니다. 이때 방문한 정점으로는 이동 할 수 없고 갈 수 있는 정점중 가장 가중치가 작은 정점으로 이동하므로 우선순위 큐를 이용하여 구현을 합니다. bfs방식과 유사하다고 볼 수 있습니다.

 

다음은 코드입니다. 먼저 크루스칼 알고리즘입니다.

 

/*크루스칼 
  가중치가 가장 작은 간선부터 시작하여 사이클이 생기지 않는 가중치가 그다음으로 작은 간선을
  추가 시키며 MST를 완성 하는 알고리즘 ElogE의 시간복잡도를 가진다.
  E의 수가 작다면 크루스칼 E의 수가 많다면 프림을 사용하는 것이 효율적임이 자명하다. 
*/

#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(false); cin.tie(NULL);
	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;
}

 

다음은 프림 알고리즘입니다.

 

#include <iostream>
#include <vector>
#include <queue>
#define P pair<int, int>

using namespace std;

int visited[10001];
vector<P> edge[10001];
/* 프링 알고리즘
   우선순위 큐를 이용하여 방문할 수 있는 정점중 가중치가 가장 낮은 정점으로 이동 
   프림은 ElogV 의 시간복잡도 
*/ 
int prim() {
	long long ans = 0;
	priority_queue<P, vector<P> , greater<P>>pq; // first는 가중치 second 는 정점 minheap 
	pq.push(P(0, 1)); //1번 정점부터 시작       // 가중치가 가장작은것이 top으로 가게된다! 
	
	while(!pq.empty()) {
		P cur = pq.top();
		pq.pop();
		
		if(visited[cur.second]) //방문 정점 표시 
			continue;
		visited[cur.second] = 1; 
		
		ans += cur.first;
		
		for (int i = 0; i < edge[cur.second].size(); i++) { //현재 정점에서 이동 할 수 있는 방문하지 않은 정점 푸쉬 
			if (!visited[edge[cur.second][i].second]) {
				pq.push(edge[cur.second][i]);
			}
		}
	}
 	return ans;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int V, E;
	cin >> V >> E;
	
	for(int i = 0; i < E; i++) {
		int A,B,C;
		cin >> A >> B >> C;
		edge[A].push_back(P(C, B));
		edge[B].push_back(P(C, A));
	}
	
	long long result = prim();
	cout<< result;
	return 0;
}