Prim 알고리즘

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;

	//다익스트라랑 거의 유사함. 단, 다익스트라는 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);
		}
	}
}