🙇‍♀️Kruskal 알고리즘

kruskal알고리즘은 disjointset을 활용한다.

class DisjointSet
{
public:
	DisjointSet(int n) : _parent(n), _rank(n, 1)
	{
		for (int i = 0; i < n; ++i)
			_parent[i] = i;
	}

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

		// 대장이 같다.
		if (u == v)
			return;

		if (_rank[u] > _rank[v])
			swap(u, v);

		_parent[u] = v;

		if (_rank[u] == _rank[v])
			_rank[v]++;
	}

private:
	vector<int> _parent;
	vector<int> _rank;
};

kruskal알고리즘의 목표가 그래프에서 최소비용으로 모든 구역을 지나갈 수 있게 길을 만드는 것이다.

세팅으로 정점이 6개 있고 정점에서 정점까지 연결가능 정보가 주어진다.

struct Vertex
{
    // 정점
	// int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

    // 정점 연결 정보
	adjacent[0][1] = adjacent[1][0] = 15;
	adjacent[0][3] = adjacent[3][0] = 35;
	adjacent[1][2] = adjacent[2][1] = 5;
	adjacent[2][3] = adjacent[3][2] = 10;
	adjacent[3][4] = adjacent[4][3] = 5;
	adjacent[3][5] = adjacent[5][3] = 10;
	adjacent[4][5] = adjacent[5][4] = 5;
}

struct CostEdge
{
	int cost, u, v;
	bool operator<(const CostEdge& other)
	{
		return cost < other.cost;
	}
};

int Kruskal(vector<CostEdge>& selected)
{
    // selected에 만들어진 그래프가 들어가게 됨.
	int res = 0; // 최소비용 구하기

	selected.clear();

	vector<CostEdge> edges;

	for (int u = 0; u < adjacent.size(); ++u)
	{
		for (int v = 0; v < adjacent[u].size(); ++v)
		{
            // 현재 양방향 그래프인데 한쪽만 필요해도 되니까
			if (u > v)
				continue;

			int cost = adjacent[u][v];
			if (cost == -1) // 이어져있지 않다.
				continue;

			edges.push_back({ cost, u, v });
		}
	}

    // kruskal은 최소비용부터 먹어가는 형식이니까 정렬이 필요함.
	sort(edges.begin(), edges.end());

    // 정점의 개수만큼 셋
	DisjointSet sets(vertices.size());

	for (CostEdge edge : edges)
	{
        // 대장이 같을 때 스킵안하면 사이클이 발생
		if (sets.Find(edge.u) == sets.Find(edge.v))
			continue;

        // 합쳐주기
		sets.Merge(edge.u, edge.v);
		selected.push_back(edge);
		res += edge.cost;
	}

	return res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

class DisjointSet
{
public:
	DisjointSet(int n) : _parent(n), _rank(n, 1)
	{
		for (int i = 0; i < n; ++i)
			_parent[i] = i;
	}

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

		// 대장이 같다.
		if (u == v)
			return;

		if (_rank[u] > _rank[v])
			swap(u, v);

		_parent[u] = v;

		if (_rank[u] == _rank[v])
			_rank[v]++;
	}

private:
	vector<int> _parent;
	vector<int> _rank;
};

struct Vertex
{
	// int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

	adjacent[0][1] = adjacent[1][0] = 15;
	adjacent[0][3] = adjacent[3][0] = 35;
	adjacent[1][2] = adjacent[2][1] = 5;
	adjacent[2][3] = adjacent[3][2] = 10;
	adjacent[3][4] = adjacent[4][3] = 5;
	adjacent[3][5] = adjacent[5][3] = 10;
	adjacent[4][5] = adjacent[5][4] = 5;
}

struct CostEdge
{
	int cost, u, v;
	bool operator<(const CostEdge& other)
	{
		return cost < other.cost;
	}
};

int Kruskal(vector<CostEdge>& selected)
{
	int res = 0;

	selected.clear();

	vector<CostEdge> edges;

	for (int u = 0; u < adjacent.size(); ++u)
	{
		for (int v = 0; v < adjacent[u].size(); ++v)
		{
			if (u > v)
				continue;

			int cost = adjacent[u][v];
			if (cost == -1)
				continue;

			edges.push_back({ cost, u, v });
		}
	}

	sort(edges.begin(), edges.end());

	DisjointSet sets(vertices.size());

	for (CostEdge edge : edges)
	{
		if (sets.Find(edge.u) == sets.Find(edge.v))
			continue;

		sets.Merge(edge.u, edge.v);
		selected.push_back(edge);
		res += edge.cost;
	}

	return res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	

	return 0;
}

참고