[Greedy Approach 예제] 백준 1197 (kruskal)

문제

1197번: 최소 스패닝 트리

---

문제 풀이

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;
	}
};

//initial : n개의 부분집합을 초기화하고 하나의 원소들이 들어가잇도록 한다.
//find(i) : point 만들기 
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;//edge값은 세번째 인자이니까.
}
int main() {
	cin >> V >>  E;
	vector<edge> v;

	for (int i = 1; i <= V; i++) {
		parent[i] = i;
	}//(1) vertex들의 모임, Initial(). 하나의 set에 하나의 원소들어간다.
	int A, B, C;
	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);//(2) edge 오름차순 정렬

	for (auto vertex : v) {
		if (find(vertex.v) != find(vertex.u)) {//(3) 같은 set에 있는지 확인한다.
			merge(vertex.u, vertex.v);//(4) 다른 set인 경우 merge
			ans += vertex.w;//
		}
	}
	cout << ans;
	return 0;

---

find, merge 함수

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;
}

find() : 해당 원소가 어느 set에 있는지 찾고 set의 부모노드를 반환한다

merge() : 찾은 두개의 원소를 같은 set에 넣어야 한다. 두번째 노드의 부모노드를 첫번째 원소로 대입해 연결시킨다.