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

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

Prim 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@9b505b2

 

결과물

 

 

---

 

 

크루스칼 알고리즘과 거의 유사하다. 다른 부분은 간선을 어떻게 수집할 것인지 순서가 달라진다.

 

크루스칼 알고리즘은 탐욕적인 방법을 이용했다. 작은 간선부터 탐색해서 사이클이 발생하지 않는 간선을 추가해줬다. 위처럼 그룹을 나누다가 경우에 따라 그룹을 병합했다.

 

프림 알고리즘은 하나의 시작점으로 구성된 트리에 간선을 하나씩 수집하며 진행한다. 예를 들어 시작점을 정한 상태에서 15와 35 중 더 작은 값인 15를 연결한다. 이런 식으로 조금씩 확장해나간다.

 

다익스트라와 굉장히 유사하다. 다익스트라는 BFS + "가중치"의 개념으로, 시작점으로부터 무조건 가까운 정점을 방문하다고 했다. 그래서 길찾기와 같이 시작점을 기준으로 어떤 거리를 판별하는데 사용한 것이기 때문에, 모든 것을 시작점을 기준으로 생각한다. (15 + 5 = 20)

다만 프림 알고리즘 자체는 시작점을 트리로 계산하는 것이기 때문에 트리 안에 있는 속하는 모든 애들을 기준으로 계산하게 된다. (15로 연결된 트리를 기준으로 가까운 것은 5)

 

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;

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

	// 다익스트라랑 거~의 유사함. 단!
	// - 다익스트라에서는 best가 [시작점]을 기준으로 한 cost
	// - 프림에서는 best가 [현재 트리]를 기준으로 한 간선 cost

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