78. 원더랜드(Kruskal MST 알고리즘 : Union & Find 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★

HongongHB 2023. 8. 23. 01:03

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int ch[1001];

struct Edge
{
	int node[2]; // 연결할 두 노드 
	int cost; // 가중치 값 
	
	Edge(int x, int y, int z)
	{
		this -> node[0] = x;
		this -> node[1] = y;
		this -> cost = z;	
	}
	
	bool operator<(const Edge &a) const
	{
		return this -> cost < a.cost; // 크루스칼 알고리즘은 오름차순을 이용한다 
	}
	
};

int Find(int x)
{
	if(ch[x] == x) return x; // 마지막으로 도달한 루트 노드를 반환
	else return Find(ch[x]); // 루트 노드가 아니라면 찾을 때까지 재귀함수 호출 
}

void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if(x < y) ch[y] = x; // 두 노드가 연결될 때 더 작은 값을 체크배열 ch에 넣는다. 
	else ch[x] = y; 
}

bool IsCycle(int x, int y) // 크루스칼 알고리즘은 cycle이 없어야한다.
// ex) a - b, b - c, c - a 와 같은 연결관계가 있어서는 안 됨. 
{
	x = Find(x);
	y = Find(y);
	if(x == y) return true;
	else return false;
}

int main()
{
	int v, e, a, b, c, cost = 0;
	scanf("%d %d", &v, &e);
	
	for(int i = 1; i <= v; i++)
		ch[i] = i; // 각 노드의 루트 노드를 자기자신으로 초기화
	
	vector<Edge> V;
	for(int i = 1; i <= e; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		V.push_back(Edge(a, b, c));
	}
	
	sort(V.begin(), V.end()); // 크루스칼 알고리즘은 오름차순을 함으로 시작 
		
	for(int i = 0; i < V.size(); i++)
	{
		int fn = V[i].node[0];
		int sn = V[i].node[1];
		int _cost = V[i].cost;
		
		if(!IsCycle(fn, sn))
		{
			cost += _cost;
			Union(fn, sn);
		} 
	}
	
	printf("%d", cost);
	return 0;
}

Kruskal Algorithm : 크루스칼 알고리즘이라고도 불리는 이 알고리즘은 전체 노드를 최소비용으로 모두 연결하는 알고리즘을 말한다. 크루스칼 알고리즘은 최소 비용 신장 트리(Minimal Spanning Tree, MST)를 구하는 대표 알고리즘이다. 신장 트리(Spanning Tree)는 기존 그래프의 모든 노드를 포함하지만 싸이클이 존재하지 않는 그래프 트리를 말한다. 이 알고리즘은 Prim Algorithm 과 다르게 간선을 중심으로 정렬해서 연결하며, 간선이 적은 신장 트리에 사용할 때 좋다.

노드는 총 7개가 있고 노드를 연결하는 간선은 11개이다.

크루스칼 알고리즘은 싸이클이 발생하지 않는다. 싸이클이 발생하는지 안 하는지 여부를 확인하기 위해서는 다음과 같은 과정을 거친다.

노드의 최종 부모를 가리키는 ch 배열 이 있다. 각 노드는 처음에는 자기 자신을 root 노드로 한다.

ex) ch[1] = 1, ch[2] = 2

두 노드를 연결하면 둘 중 작은 값을 가진다.

ex) 1번 노드와 2번 노드가 연결되면 ch 배열의 [2]는 1의 값을 가진다.

크루스칼 알고리즘은 각 간선을 오름차순으로 정렬하는 것으로 시작한다.

12(1, 7)	//거리12인 1과 7을 연결하는 간선

20(4, 7)

21(2, 4)

23(1, 4)

26(1, 2)

29(3, 5)

30(5, 6)

36(2, 3)

37(3, 6)

45(2, 5)

55(3, 7)

12(1, 7)	//연결

20(4, 7)	//연결

21(2, 4)	//연결

23(1, 4)

26(1, 2)

29(3, 5)

30(5, 6)

36(2, 3)

37(3, 6)

45(2, 5)

55(3, 7)

이제 1과 4를 연결할 차례이지만, 1과 4를 연결하면 싸이클이 발생한다. 따라서 1과 4를 연결하는 간선은 연결하지 않는다.

이후 반복하면 다음과 같다.

여기까지 크루스칼 알고리즘의 동작방식이었는데, 정리하면 다음과 같다.

노드의 최종 부모를 가리키는 ch 배열 이 있다. 각 노드는 처음에는 자기 자신을 root 노드로 한다.

ex) ch[1] = 1, ch[2] = 2 -> 초기화

두 노드를 연결하면 둘 중 작은 값을 가진다. 연결하기 전에 먼저 싸이클이 발생하는지 확인한다.

ex) 1번 노드와 2번 노드가 연결되면 ch 배열의 [2]는 1의 값을 가진다.

크루스칼 알고리즘은 각 간선을 오름차순으로 정렬하는 것으로 시작한다. 가장 적은 비용의 간선부터 차례대로 연결하기 위함이다. (최소 비용으로 연결하는 알고리즘이기 때문)