22.07.24

79. 원더랜드(Prim MST 알고리즘 : priority_queue 활용)

78 번과 동일하지만, priority_queue를 활용해 푸는 문제였다.
78번은 최소비용 도로부터 사이클을 형성하는지 확인한 후 포함시키는 구조였다면, 이번에는 하나의 도시에서 가지를 뻗어나가는 형식으로 풀었다.
1번도시에서 시작한다고 가정하고, 1번과 연결된 도시를 priority_queue에 넣어서 최소 비용으로 가는 도시를 선택한다.
이후 그 도시에서 갈 수 있는 도시를 또 priority_queue에 추가하여 1번 + 다음 도시에 연결된 도시들 중 최소비용을 선택한다.
이 과정에서 이미 온 적이 있는 도시는 체크를 해가면서 각 도시당 한 번만 방문하도록 설계하면 문제를 해결할 수 있다.

일주일만에 알고리즘 문제를 풀었는데, 저번에 이 문제를 풀다가 잠깐 강의를 봤던 기억을 되짚어가면서 문제를 풀었다.

하루에 한 문제 푸는 게 생각보다 마음대로 안된다..

int main(){
	
	//freopen("input.txt","rt",stdin);

	int k, e, a, b, c;
	cin>>k>>e;
	priority_queue<Data> pQ;
	vector<int> cnt(26,0);
	vector<vector<Data>> city(26);
	
	
	
	for(int i=0; i<e; i++){
		cin>>a>>b>>c;
		city[a].push_back(Data(a,b,-c));
		city[b].push_back(Data(b,a,-c));
	}
	
	int tmp = 1, answer = 0;
	int num = 1; 
	cnt[1]=1;
	while(tmp<k){
		
		for(int i=0; i<city[num].size(); i++){
			pQ.push(city[num][i]);
		}
	
	while(cnt[pQ.top().n2]!=0){
		
		pQ.pop();
	}
	answer-=pQ.top().cost;
	cnt[pQ.top().n2] = 1;
	num = pQ.top().n2;
	
	tmp++;
	}
	

	cout<<answer;
	
	return 0;