[C++ 자/알 Note] Kruskal 알고리즘 적용 (미로 생성)

주의 사항

미로 맵을 생성하는 경우에

Kruskal 알고리즘을 사용하면 쉽게 맵을 생성할 수 있다

 

코드에 앞서

기본적으로 타일은 WALL(빨강)과 EMPTY(초록)로 구분되어 있다

Kruskal 알고리즘을 적용하기 전에

y와 x의 2의 배수 위치에는 모두 WALL로 처리한다

이렇게 하면 아래와 같이 된다

 

그리고 각 간선들을 vector로 push_back 해주는데

여기서 각각 간선들의 가중치를 랜덤 하게 넣어준다

 

이렇게 준비를 마치면,

vector를 sort해서 가중치가 적은 순으로 정렬한다

그리고 Disjoint의 Find와 Merge를 이용해서

사이클을 방지하며 길을 뚫어주면 된다

 

구현 코드

void Board::GenerateMap_Kruskal()
{
	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;
	}
}