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

ㅂ크루스칼 알고리즘과 Union Find 알고리즘을 연습하기 좋은 문제다. 

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

1197번: 최소 스패닝 트리

크루스칼 알고리즘은 Greedy 알고리즘의 일종으로, 트리의 간선을 오름차순으로 정렬한 후 가중치가 가장 적은 간선부터 cycle이 생기기 전까지 차례로 합집합으로 만들어나가는 알고리즘이다. 

cycle의 생성 유무는 Union-Find 알고리즘으로 확인할 수 있다. 간선 정보를 담기위해 배열을 선언하는 방식에는 다양한 종류가 있지만, Class를 직접 선언하여 vector로 다루는게 직관성이 좋을 것 같아 나동빈님의 크루스칼 알고리즘 블로그를 참조하여 구현하였다.

https://m.blog.naver.com/ndb796/221230994142 

18. 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘 구현 Check Point
1. 두 정점과 간선을 저장할 배열
2. 해당 정점의 부모 노드를 저장할 배열
3. 두 정점이 동일한 부모 노드를 가지는지 확인할 find 메소드
4. 두 정점이 동일하지 않다면 부모 노드를 통합할 union 메소드

 

class를 생성해 구현한 크루스칼 알고리즘 구현 코드 예제

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

using namespace std;
int parent[10001];

void initialization(int V) {
	for (int i = 0; i < V; i++) {
		parent[i] = i;
	}
}

class Edge {
public:
	int node[2];
	int distance;

	Edge(int a, int b, int distance) {
		this->node[0] = a;
		this->node[1] = b;

		this->distance = distance;
	}
	bool operator < (Edge& edge) {
		return this->distance < edge.distance; // 현재 distance가 더 적다면 true 로 반환
	}
};
int getParent(int a) {
	if (parent[a] == a) return a; //찾고자하는 노드가 부모노드로 되어있다면 부모노드 반환
	return parent[a] = getParent(parent[a]); // 찾고자하는 노드가 부모노드가 아니라면 a 에 저장되어있는 부모노드의 부모노드를 찾아 저장한다(초기화와 동시에 find)
} 

void UnionParent(int a,int b) {
	a = getParent(a);  
	b = getParent(b); // a,b 두 정점의 부모 노드를 찾는다
	if (a < b) parent[b] = a; // 더 작은 정점을 기준으로 부모노드를 저장한다.(합집합)
	else parent[a] = b; 
}

bool Find(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a == b) return true; // 부모노드가 동일할 경우 true 반환 
	else return false; // 부모노드가 다를 경우(사이클이 생기지 않음) false 반환 
}

vector<Edge> v;

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

	int V, E;
	int v1, v2, w;
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		cin >> v1 >> v2 >> w;
		v.push_back(Edge(v1, v2, w));
	}

	int sum = 0;
	sort(v.begin(), v.end());
	
	initialization(V);

	for (int i = 0; i < v.size(); i++) {
		if (!Find(v[i].node[0], v[i].node[1])) { // 두 정점의 부모노드가 다를 경우
			sum += v[i].distance; // 가중치를 더하고 
			UnionParent(v[i].node[0], v[i].node[1]); // 두 정점을 합집합으로 변경
		}
	}
		
	cout << sum << "\n";

}

부모노드를 찾는 getfparent 메소드에서의 재귀함수를 이해하고, 두 정점과 간선을 저장할 배열을 구현할 줄 안다면 쉽게 풀 수 있는 간단한 문제!