[Algorithm] Kruskal Algorithm(크루스칼 알고리즘)

• 이 글은 (https://m.blog.naver.com/ndb796/221230994142) 블로그를 보고 작성하였습니다.

Kruskal Algorithm

크루스칼 알고리즘은 연결된 그래프에서 가장 최소 비용을 사용하여 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 다른 말로는 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다.

프로그래머스 (https://programmers.co.kr/learn/courses/30/lessons/42861?language=cpp) 이 문제를 예시로 들어 설명하도록 하겠습니다.

크루스칼 알고리즘을 쓰기 위한 핵심 개념은 크게 3가지가 존재합니다.

1. 최소 비용 순서에 맞게 간선들을 정렬시킵니다.
2. 정렬된 순서에 맞게 그래프에 포함시키는데 포함시키기 전에는 사이클 테이블을 확인합니다.
3. 사이클을 형성한 경우는 포함시키지 않습니다.

사이클을 형성 여부는 union-find 알고리즘을 사용하여 같은 그래프로 연결되어 있는지를 확인하여 알 수 있습니다.

예시

다음 노드를 가지고 최소 비용 순서에 맞게 간선들을 정렬시킵니다.

그리고 정렬된 순서에 맞게 그래프에 포함시킵니다. 다음 예시를 확인할 때 (0, 1) -> (1, 3) -> (0, 2) 순서대로 포함하면 답이 나오는 구조가 됩니다.

해당 그래프가 union-find 알고리즘을 사용하면 모두 같은 부모 노드를 가리키기 때문에 그 뒤 간선들은 무시하면 됩니다.

이 예와 다르게 정렬된 순서대로 진행하다가 비교 노드끼리 같은 그래프라고 판단하면 건너뛰고 다음 간선부터 포함여부를 확인하면 됩니다.

코드

	#include <string>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	// 크루스칼 알고리즘으로 해결
	// 엣지 표현하기 위한 클래스
	class Edge{
	public:
	int s,e,c;
	Edge(int s,int e,int c):s(s),e(e),c(c){};
	};
	// 엣지 최소 비용순으로 정렬
	bool cmp(Edge a, Edge b){
	return a.c < b.c;
	}
	// union-find에서 부모노드 찾기
	int getParent(int parent[], int x){
	if(x == parent[x]){return x;}
	return parent[x] = getParent(parent,parent[x]);
	}
	// union-find 부모노드 합치기
	void unionParent(int parent[], int a, int b){
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a<b){
	parent[b] = a;
	}
	else{
	parent[a] = b;
	}
	}
	// union-find 부모노드 같은지 찾기
	int findParent(int parent[], int a, int b){
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a == b)return 1;
	else return 0;
	}
	int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	int check[100];
	for(int i=0;i<100;i++){
	check[i] = i;
	}
	// 각 정점을 vec에 넣고 비용이 적은 간선부터 정렬한다.
	vector<Edge> vec;
	for(int i=0;i<costs.size();i++){
	Edge e = Edge(costs[i][0],costs[i][1],costs[i][2]);
	vec.push_back(e);
	}
	sort(vec.begin(),vec.end(),cmp);
	// 각 노드들 관계가 사이클이 없으면 추가한다.
	for(int i=0;i<vec.size();i++){
	if(!findParent(check, vec[i].s, vec[i].e)){
	unionParent(check, vec[i].s, vec[i].e);
	answer+=vec[i].c;
	}
	}
	return answer;
	}

view raw Programmers Lv3.land connection.cpp hosted with ❤ by GitHub

• 추가로 궁금한 점이나 수정할 부분이 있으면 댓글로 남겨주세요.