Inflearn Community Q&A

두가지 질문이 있습니다.

1. Prim으로 맵 생성할 때 best가 왜 필요한 것인지 이해가 잘 되지 않아서 질문 드립니다. 제 생각으로는 트리와 연결된 간선들 중 어차피 가장 작은 가중치를 가지는 간선을 선택할 텐데 그걸 굳이 best로 저장하고 갱신시킬 필요가 있는 것인지...잘 모르겠습니다.

2. 또 선택한 정점과 연결된 간선들을 discovered에 넣는 부분에서 굳이 새로 발견한 정점이 있다면 continue해야 하는 이유도 잘 모르겠습니다. 그 위에서 트리에 있었다면 continue하는 부분 만으로 충분하다고 생각되어서요.

참고로 두 부분을 빼도 맵은 잘 작동하기에 더욱 이해가 되질 않아 질문합니다!

// 어떤 정점이 트리에 포함되어 있나?
	map<Pos, bool> tree;
	// 정점의 부모는 누구인가?
	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;
			tree[Pos{ y,x }] = false;
		}
	}

	priority_queue<CostEdge, vector<CostEdge>, greater<CostEdge>> discovered;

	const Pos startPos = Pos{ 1,1 };  // 랜덤으로 정해도 됨.
	discovered.push(CostEdge{ startPos, 0 });
	parent[startPos] = startPos;
	best[startPos] = 0;

	while (discovered.empty() == false)
	{
		CostEdge bestEdge = discovered.top();  // 가중치 가장 작은 간선을 선택
		discovered.pop();

		// 새로 연결된 정점
		Pos v = bestEdge.vertex;
		if (tree[v] == true)  // 만약 트리에 v가 이미 있었다면 continue
			continue;

		tree[bestEdge.vertex] = true;
		
		// 맵에 적용
		// 이전 정점(= 새로 연결된 정점의 부모)
		Pos u = parent[v];

		int y = (u._y + v._y) / 2;
		int x = (u._x + v._x) / 2;

		_tile[y][x] = TileType::EMPTY;

		for (const CostEdge& e : edges[bestEdge.vertex])  // 선택한 정점과 연결된 간선들을 discovered에 넣음.
		{
			if (tree[e.vertex])  // 새로 발견한 애들이 이미 있었다면 continue
				continue;

			if (e.cost > best[e.vertex])  // 다른 경로로 더 좋은 후보가 발견되었으면 continue
				continue;

			discovered.push(e);
			parent[e.vertex] = bestEdge.vertex;
			best[e.vertex] = bestEdge.cost;
		}

	}