[C/C++] 백준 1197번 - 최소 스패닝 트리 (MST, 프림, 크루스칼 알고리즘)

 

 

<크루스칼 알고리즘 코드>

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

int V, E, A, B, C;
int u, v, w;
int parent[10001];
long long ans;
bool check;
vector<tuple<int, int, int>> graph;

int find_parent(int x)
{
	if (parent[x] == x) // 자기자신이 부모일 경우 
		return x;
	else // 부모 노드 찾기
		return parent[x] = find_parent(parent[x]);
}

void union_node(int u, int v)
{
	check = false;

	u = find_parent(u);
	v = find_parent(v);

	if (u == v) // 부모가 같다면 결합 시 사이클 이므로
		return; // 연결하지 않는다.
	else
	{
		parent[u] = v; // 결합 & 부모로 기록
		check = true;
	}
}

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

	cin >> V >> E;

	// 부모를 자기 자신으로 초기화
	for (int i = 1; i <= V; i++)
		parent[i] = i;

	// 그래프 정보 저장
	for (int i = 0; i < E; i++)
	{
		cin >> A >> B >> C;
		graph.push_back(make_tuple(C, A, B));
	}
	
	// 가중치가 작은 간선부터 오름차순으로 정렬
	sort(graph.begin(), graph.end());

	// 간선들 결합 (MST 찾기)
	for (int i = 0; i < E; i++)
	{
		/*
		get<0>(graph[i] : 가중치
		get<1>(graph[i] : 출발 노드
		get<2>(graph[i] : 도착 노드
		*/
		union_node(get<1>(graph[i]), get<2>(graph[i]));

		if (check) ans += get<0>(graph[i]); // 가중치 더하기
	}

	cout << ans << '\n';
}

 

<프림 알고리즘 코드>

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

typedef pair<int, int> pair_ii;

int V, E, A, B, C;
int u, v, w;
long long ans;
bool visit[10001];
vector<pair_ii> graph[10001];
priority_queue<pair_ii, vector<pair_ii>, greater<pair_ii>> pq; // 오름차순 우선순위 큐

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

	cin >> V >> E;

	// 그래프 연결 정보 저장
	for (int i = 0; i < E; i++)
	{
		cin >> A >> B >> C;
		graph[A].push_back(make_pair(B, C));
		graph[B].push_back(make_pair(A, C));
	}

	pq.push(make_pair(0, 1)); // (가중치, 노드)

	while (!pq.empty())
	{
		int now_weight = pq.top().first;
		int now_node = pq.top().second;
		
		pq.pop();

		// 이미 방문했으면 넘어감
		if (visit[now_node]) continue;

		visit[now_node] = true; // 방문 표시

		ans += now_weight;

		// 다음 정점들을 우선순위 큐에 삽입
		for (int i = 0; i < graph[now_node].size(); i++)
		{
			int next_node = graph[now_node][i].first;
			int next_weight = graph[now_node][i].second;

			pq.push(make_pair(next_weight, next_node));
		}
	}
	cout << ans << '\n';
}

 

 

풀이 방법

 

크루스칼 알고리즘은 모든 간선에 대해서 가중치가 작은 간선들부터 연결해주되 중간중간에 사이클이 생기게 된다면 건너뛰고 다음 간선을 연결하여 최소 스패닝 트리를 만들어가는 알고리즘입니다.

그리고 프림 알고리즘은 하나의 정점을 시작점으로 하고 시작점과 연결된 정점들에 연결된 간선들중 가중치가 작은 간선들을 서로 연결해주면서 확장시켜나가 최소 스패닝 트리를 만들어가는 알고리즘입니다. 

크루스칼 알고리즘 시간 복잡도 : O(ElogE)

프림 알고리즘 시간 복잡도 : O(ElogV)

 

처음에 문제를 접했을 때는 최소 스패닝 트리(MST)의 풀이법에 대한 지식(프림, 크루스칼 알고리즘)이 별로 없어 엉뚱하게 다익스트라 알고리즘으로 풀이를 하려다가 Crocus님의 포스팅을 보고 문제를 풀이하였습니다.

 

 

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리