[MST] Chapter 03. Kruskal 알고리즘을 이용한 맵 생성

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ea4d99bf27f79da3e7b4f924d6e2ca50d9c63744

Kruskal 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@ea4d99b

 

결과물

 

 

---

 

 

미로라면, 랜덤성이 보장이 되야하는데 코드 특성상 아래랑 우측이 일직선으로 뚫린 현상으로 맵이 만들어지게 했었다.

이 부분을 개선시키기 위해 Kruskal 알고리즘을 이용한 맵 생성을 해볼 것이다.

 

---

 

최초의 상태

Kruskal을 어떻게 응용할 지 생각해보면 BST를 만들 때, 어떻게 만들었는지를 생각해보자.

이전까지 Binary Tree 알고리즘에 대해선 우측 혹은 아래 즉, 1/2 확률로 길을 뚫어주는 형식으로 만들었다. 

 

이제 크루스탈 알고리즘이라 생각해보면 뚫려있는 초록색 점이 정점이라고 생각해보자. 그리고 갈 수 있는 모든 후보들을 선택한다(우측 혹은 아래). 양 옆에 후보들을 간선이라고 간주하고, 간선들의 cost를 랜덤으로 세팅할 것이다.

그럼 갈 수 있는 간선들이 후보군에 들어가겠지만, 각각 cost가 다르기 때문에 Kruskal 알고리즘을 적용시키면 최소 스패닝 트리가 만들어지면서 결국은 cost의 합이 최소가 되는 형식으로 길이 뚫리게 될 것이다.

 

cost를 랜덤으로 세팅할 것이기 때문에, 길이 랜덤으로 만들어지게되면서 과거의 아래랑 우측이 일직선으로 뚫린 현상이 없어질 것이다. 

 

// Binary Tree 미로 생성 알고리즘
// - Mazes For Programmers
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;
	}
}