[C++ algorithm] 최소 스패닝 트리(Minimum Spanning Tree)

Disjoint Set

상호 배타적 집합은 최소 스패닝 트리를 배울 때 매우 좋은 역할을 하기 때문에 미리 알아보자.

다른 이름으로는 Union-Find라고 부른다.

예를 들어, 리지니라는 게임이 인기가 있고 배그가 인기가 있으니 리비지 배틀그라운드 라는 혼종 게임을 만들자고 해보자.

혈맹전 + 서바이벌을 같이 하는 것이다.

그래서 생각해보면

 

1인 팀 1000명(팀 id 0~999)가 있고 동맹을 맺을 수 있다.(1번팀 + 2번팀 을 동맹하면 = 1번팀으로 합쳐진다)

우리가 만약 vector 자료구조만 알고 있다고하면 다음과 같이 코딩을 할 것이다.

void LineageBattleground()
{
	struct User
	{
		int temaId;
		// TODO
	};

	// TODO : UserManager
	vector<User> users;
	for (int i = 0; i < 1000; i++)
	{
		users.push_back(User{ i });
	}
	// 게임 진행
	// users[1] <-> users[5] 동맹 맺음
	users[5].temaId = users[1].temaId;

	// 만약 1 : 1로 합병하는게 아닌
	// temaid = 1인 팀과 temaid = 2 인 팀이 통합한다고 하면
	for (User& user : users)
	{
		if (user.temaId == 1)
			user.temaId = 2;
	}
}

만약 유저수가 정말 많아지면 연산량이 많아 매우 비효율적이다.

 

따라서 트리 구조를 이용한 상호 배타적 집합의 표현을한다.

class NavieDisjointSet
{
public:
	NavieDisjointSet(int n) : _parent(n)
	{
		for (int i = 0; i < n; i++)
		{
			_parent[n] = i;
		}
	}
	// 니 대장이 누구니??
	int Find(int u)
	{
		if (u == _parent[u])
			return u;
		return Find(_parent[u]);
	}
	// 동맹 맺기
	void Merge(int u, int v)
	{
		u = Find(u);
		v = Find(v);

		if (u == v)
			return;

		_parent[u] = v;
	}

private:
	vector<int> _parent;
};

// 트리가 한쪽으로 기우는 문제를 해결?
// 트리를 합칠 때, 항상 높이가 낮은 트리를 높이가 높은 트리 밑으로 합치기
// Union-By-Rank, 랭크(높이)에 의한 합치기 최적화
class DisjointSet
{
public:
	DisjointSet(int n) : _parent(n), _rank(n, 1)
	{
		for (int i = 0; i < n; i++)
		{
			_parent[n] = 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);

		// rank[u] <= rank[v] 보장됨

		_parent[u] = v;

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

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

처음에 했던 방식보다 훨씬 우아하고 효율적이게 작동할 수 있다.

최소 스패닝 트리

우리가 이전에 그래프에 대해 공부한적있다. 스패닝 트리는 간선의 수를 최소화해서 모든 수의 정점을 연결하는 것이다. 스패닝 트리는 사이클을 포함하면 안된다. 그러나 다양한 모습으로 나타날 수 있다. N개의 정점을 연결하기 위해서는 N-1개의 간선이 필요할 것이다.

최소 스패닝 트리는 간선 가중치에 따라 모든 비용을 최소화해서 스패닝 트리를 만드는 것이다. 

대표적으로 크루스칼(Kruskal) 알고리즘이 있다. 특징은 Greedy 방법을 이용한다. 

지금 이 순간에 최적인 답을 선택하여 결과를 도출하자는 의미이다.

그룹 단위로 관리를 하면 쉽게 관리할 수 있다.

그렇기 때문에 우리가 위에서 상호 배타적 집합, Disjoint Set을 알아본 것이다.

그래프로 나타내보자.

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
class DisjointSet
{
public:
	DisjointSet(int n) : _parent(n), _rank(n, 1)
	{
		for (int i = 0; i < n; i++)
			_parent[i] = i;
	}

	// 조직 폭력배 구조?
	// [1]		[3]
	// [2]	 [4][5][0]
	// 		    

	// 니 대장이 누구니?
	int Find(int u)
	{
		if (u == _parent[u])
			return u;

		//_parent[u] = Find(_parent[u]);
		//return _parent[u];

		return _parent[u] = Find(_parent[u]);
	}

	// u와 v를 합친다
	void Merge(int u, int v)
	{
		u = Find(u);
		v = Find(v);

		if (u == v)
			return;

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

		// rank[u] <= rank[v] 보장됨
		_parent[u] = v;

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

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

struct Vertex
{
	// 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[1][3] = adjacent[3][1] = 10;
	adjacent[3][4] = adjacent[4][3] = 5;
	adjacent[3][5] = adjacent[5][3] = 10;
	adjacent[5][4] = adjacent[4][5] = 5;
}

struct CostEdge
{
	int cost;
	int u;
	int v;

	bool operator<(CostEdge& other)
	{
		return cost < other.cost;
	}
};

int Kruskal(vector<CostEdge>& selected)
{
	int ret = 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(CostEdge{ cost, u ,v });
		}
	}
	std::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);
		ret += edge.cost;
	}

	return ret;
}

int main()
{
	CreateGraph();

	vector<CostEdge> selected;
	int cost = Kruskal(selected);
}

Kruskal 알고리즘을 이용한 맵 생성

우리가 이전에 만들던 미로 게임에서 맵을 생성하는 방식은 이진트리 방식으로 미로를 생성했다.

아쉬운점은 알고리즘 특성상 맨 마지막 줄은 쭉 뚫려있게 된다. 

이걸 Kruskal 알고리즘을 통해 해결해보자.

void Board::GenerateMap()
{
	for (int32 y = 0;  y < _size;  y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
			{
				_tile[y][x] = TileType::WALL;
			}
			else
			{
				_tile[y][x] = TileType::EMPTY;
			}
		}
	}
	vector<CostEdge> edges;

	// edges 후보를 랜덤 cost로 등록한다.

	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
				continue;

			// 우측 연결하는 간선 후보
			if (x < _size - 2)
			{
				const int32 randValue = ::rand() % 100;
				edges.push_back(CostEdge{ randValue,Pos{y,x},Pos{y,x + 2} });
			}
			// 아래로 연결 하는 간선 후보
			if (y < _size - 2)
			{
				const int32 randValue = ::rand() % 100;
				edges.push_back(CostEdge{ randValue,Pos{y,x},Pos{y + 2,x} });
			}
		}
	}
	std::sort(edges.begin(), edges.end());

	DisjointSet sets(_size * _size);

	for (CostEdge& edge : edges)
	{
		int u = edge.u.y * _size + edge.u.x;
		int v = edge.v.y * _size + edge.v.x;
		// 같은 그룹이면 스킵 안그러면 사이클 발생
		if (sets.Find(u) == sets.Find(v))
			continue;

		// 두 그룹을 합친다.
		sets.Merge(u, v);
		// 맵에 적용
		int y = (edge.u.y + edge.v.y) / 2;
		int x = (edge.u.x + edge.v.x) / 2;

		_tile[y][x] = TileType::EMPTY;
	}
}

 

Prim 알고리즘을 통한 맵 생성

크루스칼이랑 다르게 하나의 시작점으로 구성된 트리에 간선을 하나씩 수집하며 진행한다. 크루스칼은 간선중 가중치 값이 제일 작은 값들을 선택하면서 진행하는 것과 다르다. 이는 다익스타라 알고리즘이랑 비슷하다. 단지 차이점은 다익스트라는 시작점을 기준으로 cost를 계산했다면 Prim은 정점 집합을 기준으로 cost를 계산한다.

void Board::GenerateMap_Prim()
{
	struct CostEdge
	{
		int cost;
		Pos vtx;

		bool operator<(const CostEdge& other) const
		{
			return cost < other.cost;
		}
	};

	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
			{
				_tile[y][x] = TileType::WALL;
			}
			else
			{
				_tile[y][x] = TileType::EMPTY;
			}
		}
	}

	// edges[u] : u 정점과 연결된 간선 목록
	map<Pos, vector<CostEdge>> edges;

	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
				continue;

			// 우측 연결하는 간선 후보
			if (x < _size - 2)
			{
				const int32 randValue = ::rand() % 100;
				Pos u = Pos{ y,x };
				Pos v = Pos{ y,x + 2 };
				edges[u].push_back(CostEdge{ randValue,v });
				edges[v].push_back(CostEdge{ randValue,u });
			}
			// 아래로 연결 하는 간선 후보
			if (y < _size - 2)
			{
				const int32 randValue = ::rand() % 100;
				Pos u = Pos{ y,x };
				Pos v = Pos{ y + 2,x };
				edges[u].push_back(CostEdge{ randValue,v });
				edges[v].push_back(CostEdge{ randValue,u });
			}
		}
	}

	// 해당 정점이 트리에 포함되어있나?
	map<Pos, bool> added;
	// 어떤 정점이 누구에의해 연결되었는지
	map<Pos, Pos> parent;
	// 만들고 있는 트리에 인접한 간선 중, 해당 정점에 닿는 최소 간섭
	map<Pos, int32> best;
	// 초기화
	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			best[Pos{y, x}] = INT32_MAX;
			added[Pos{y, x}] = false;
		}
	}

	priority_queue<CostEdge> pq;
	const Pos startPos = Pos{ 1,1 }; 
	pq.push(CostEdge{ 0,startPos });
	best[startPos] = 0;
	parent[startPos] = startPos;

	while (pq.empty() == false)
	{
		CostEdge bestEdge = pq.top();
		pq.pop();

		// 새로 연결된 정점
		Pos v = bestEdge.vtx;

		if (added[v])
			continue;
		added[v] = true;
		// 맵에 적용
		{
			int y = (parent[v].y + v.y) / 2;
			int x = (parent[v].x + v.x) / 2;
			_tile[y][x] = TileType::EMPTY;
		}

		// 방금 추가된 정점에 인접한 간선들을 검사한다.
		for (CostEdge& edge : edges[v])
		{
			if (added[edge.vtx])
				continue;
			if (edge.cost > best[edge.vtx])
				continue;

			best[edge.vtx] = edge.cost;
			parent[edge.vtx] = v;
			pq.push(edge);
		}
	}
}

위의 영상과 동일하게 랜덤한 맵을 생성한다