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

1. 문제

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

1197번: 최소 스패닝 트리

 

2. 알고리즘 분류

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

 

3. 소스 코드

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

using namespace std;

int parent[10005];
bool is_cycle;
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]);
}

// 2개의 노드를 한 그룹으로 묶는 함수
void union_node(int a, int b)
{
	// 각 정점의 부모 노드 찾기
	int pa = find_parent(a);
	int pb = find_parent(b);

	if (pa == pb) // 부모 노드가 같다 = 싸이클 (연결 X)
	{
		is_cycle = true;
	}
	else // 부모 노드가 다르다 = 싸이클 X (연결 O)
	{
		parent[pb] = pa;
		is_cycle = false;
	}

}

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

	// parent 초기화
	for (int i = 0; i < 10005; i++)
		parent[i] = i;

	// V, E 입력
	int V, E;
	cin >> V >> E;

	// 간선의 정보 입력
	for (int i = 0; i < E; i++)
	{
		int A, B, C;
		cin >> A >> B >> C;

		graph.push_back(make_tuple(C, A, B));
	}

	// 가중치 기준으로 오름차순 정렬
	sort(graph.begin(), graph.end());

	long long ans = 0;

	// 크루스칼 알고리즘
	// 가중치가 낮은 순부터 연결
	for (int i = 0; i < E; i++)
	{
		// 사이클이 발생하는지 체크
		union_node(get<1>(graph[i]), get<2>(graph[i]));

		// 사이클이 발생하지 않았다면, 연결 및 가중치 합산
		if (!is_cycle) ans += get<0>(graph[i]);
	}

	// 최소 스패닝 트리 출력
	cout << ans;

	return 0;
}

 

4. 유용한 문법/알고리즘

 1) 크루스칼 알고리즘

• 최소 가중치를 가지면서 모든 정점을 연결하는 알고리즘
• 가중치가 가장 낮은 간선부터 연결해가면서, 만약에 싸이클이 발생하면 연결하지 않는 방식

// 크루스칼 알고리즘
// 가중치가 낮은 순부터 연결
for (int i = 0; i < E; i++)
{
	// 사이클이 발생하는지 체크
	union_node(get<1>(graph[i]), get<2>(graph[i]));

	// 사이클이 발생하지 않았다면, 연결 및 가중치 합산
	if (!is_cycle) ans += get<0>(graph[i]);
}

 

 2) Union-Find

• 2개의 정점을 하나의 그룹으로 묶는 알고리즘
• Find 함수 : 해당 정점의 Root(조상)를 찾는 함수
• Union 함수 : 두 정점을 하나의 같은 Root(조상)로 묶는 함수

// 부모를 찾는 함수
int find_parent(int x)
{
	if (parent[x] == x) // 자기 자신이 부모라면, 자기 자신 출력
		return x;
	else // 최종 부모 노드 찾을 때까지 재귀함수
		return parent[x] = find_parent(parent[x]);
}

// 2개의 노드를 한 그룹으로 묶는 함수
void union_node(int a, int b)
{
	// 각 정점의 부모 노드 찾기
	int pa = find_parent(a);
	int pb = find_parent(b);

	if (pa == pb) // 부모 노드가 같다 = 싸이클 (연결 X)
	{
		is_cycle = true;
	}
	else // 부모 노드가 다르다 = 싸이클 X (연결 O)
	{
		parent[pb] = pa;
		is_cycle = false;
	}
}