6-3. 크루스칼 알고리즘을 활용한 미로 맵 만들기

0. 구상

사전에 사용했던 미로 맵을 Kruskal 알고리즘을 사용하여 만든다.

(기존의 미로 맵은 탈출구가 있던 세로 줄과 가로 줄은 모두 초록색으로 길이 뚫려 있었다)

간선을 경로로 만들고, 코스트를 랜덤으로 생성할 것이다.

Kruskal 알고리즘을 통해 코스트가 가장 작은 경로를 선택하여 도착점까지 향하도록 설정한다.

 

1. 코드 수정

1-2. 미로 만들기(2) - 오른손 법칙(우수법)

위의 포스트에서 만들었던 미로를 수정하기 위해 GenerateMap을 수정한다.

 

(1) CostEdge

6-2. 최소 신장 트리(Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm)

struct CostEdge
{
	int cost;
	Pos u; // 좌표를 가지는 노드
	Pos v;

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

그리고 이전 포스트의 CostEdge 구조체는 Board.h에 작성한다.

 

(2) 서로소 집합 ; DisjointSet

6-2. 최소 신장 트리(Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm)

#pragma once
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]) // 찾는 u가 루트 노드임
			return u;

		return _parent[u] = Find(_parent[u]); // 재귀적 호출로 위로 타고 올라가기
	}

	void Merge(int u, int v) // 합치기, u가 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;
};

이전 포스트의 DisjointSet class는 솔루션 탐색기에서 추가 - 클래스 기능을 이용해 cpp와 h 파일로 만든다.

여기에서 코드는 그냥 DisjointSet.h에 저장하고 사용할 것이다.

 

 

 

2. 크루스칼 알고리즘을 Map에 적용하기

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 후보를 랜덤 코스트로 등록
	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} });
			}

		}
	}
	// Kruskal 알고리즘
	std::sort(edges.begin(), edges.end());

	DisjointSet sets(_size * _size);

	for (CostEdge& edge : edges)
	{
		// 1차원으로 관리하는 방법
		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);

		// 맵에 적용하기
		// [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;
	}
}

 

(1) 벽 생성

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

25 x 25 맵 상의 짝수번째(0, 2, 4, 6 ...)에 붉은 픽셀로 벽을 생성한다.

(2) 알고리즘 적용을 위한 코스트 생성

	vector<CostEdge> edges;

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

		}
	}

각 정점을 체크하여 벽인 부분(짝수번째)을 만나면 함수를 빠져나온다.

맵을 보면 맵의 맨 위, 맨 아래, 맨 오른쪽, 맨 왼쪽은 무조건 벽으로 생성되어 있으므로(x == 0 || y == 0)

이 부분을 뺀 1, 3, 5, 7, 9, 11 ... 21의 정점 (위 그림에서 초록색 점들)들을

 

[1]  [벽 ] [3]   [벽]  [5]...

[벽] [25] [벽] [27] ...

[49] [벽] [51] [벽] ...

 

x 기준으로는 우측으로 벽을 건너뛴 후 정점과 연결하고 (1 -> 3, 3 -> 5 ...) 

y 기준으로는 아래쪽으로 벽을 건너뛴 후 정점과 연결한다. (1 -> 49, 3 -> 51 ...)

이 떄 코스트는 rand를 이용해 최대 두 자리 수가 된다.

 

연결된 간선의 정보를 edges 배열에

CostEdge { 코스트, 정점, 정점 옆 벽 너머의 정점 }

CostEdge { 코스트, 정점, 정점 아래 벽 너머의 정점 }

와 같이 밀어 넣는다.

 

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

	// Kruskal 알고리즘
	std::sort(edges.begin(), edges.end());

	DisjointSet sets(_size * _size);

	for (CostEdge& edge : edges)
	{
		// 1차원으로 관리하는 방법
		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);

		// 맵에 적용하기
		// [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;
	}
}

정렬된 간선을 오름차순으로 정렬한다.

그리고 보드의 25 x 25 사이즈 만큼 그룹을 구성한다.

 

CostEdge는 u와 v를 가지는데, 여기에서는 u와 v가 Pos 형으로 관리되고 있으므로, u와 v는 y와 x를 멤버 변수로 저장하고 있다(2차원).

따라서 단순히 1차원적으로 관리하기 위해 각 정점의 좌표를 계산식으로 하나로 합쳐준다.

(1 * 25 + 1 = 26, 1 + 25 + 3 = 28 ... 이므로 벽을 건너뛴 첫 줄의 정점들은 26, 28, 30, 32 ... 이 된다)

 

이어서 Find 함수를 사용하여 루트 노드가 같으면 같은 그룹인 뜻이므로 함수를 빠져나온다.

아니라면 두 그룹을 합친다.

그리고 맵에서 간선을 표현하기 위하여 두 u와 v의 중간 좌표를 초록색의 EMPTY 타일로 만들어주면 된다.