79. 원더랜드(Prim MST 알고리즘 : priority_queue 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int ch[1001];

struct Edge
{
	int node; // 연결할 노드
	int cost; // 가중치 값
	
	Edge(int x, int y)
	{
		this -> node = x;
		this -> cost = y;
	}
	
	bool operator<(const Edge &a) const
	{
		return this -> cost > a.cost; // 구조체가 우선순위큐에서 사용되면 최소힙으로 사용된다.
		// 이 멤버 함수는 구조체가 pop, push 될 때 호출되며, 호출된 a.cost가 더 작은 값이므로 최소힙이 된다
		// !! vector에서 사용하면 내림차순을 위한 조건, 우선순위큐에서 사용하면 최소힙 
	}
};

int main()
{
	int v, e, a, b, c, cost = 0;
	
	scanf("%d %d", &v, &e);
	
	vector<pair<int, int>> V[101]; // 인접 리스트
	priority_queue<Edge> pQ; // 다음 노드로 가기위한 노드 번호와 가중치를 가진 구조체
    // 최소힙으로 최소 가중치를 구하기 위해 우선순위큐를 쓴다
	
	for(int i = 1; i <= e; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		V[a].push_back(make_pair(b, c)); // 입력받은 노드와 인접한 노드, 가중치를 할당
		V[b].push_back(make_pair(a, c)); // 무방향 그래프를 위해 반대편 노드도 똑같이 할당
	}
	
	pQ.push(Edge(1, 0));
	
	while(!pQ.empty())
	{
		Edge temp = pQ.top();
		pQ.pop();
		
		int _node = temp.node; // 다음 노드번호
		int _cost = temp.cost; // 가중치 값
		
		if(ch[_node] == 0) // 연결한 노드가 없다면
		{
			ch[_node] = 1;
			cost += _cost;
			for(int i = 0; i < V[_node].size(); i++)
			{
				pQ.push(Edge(V[_node][i].first, V[_node][i].second)); // 다음 노드에서 똑같이 진행하기 위해 push
			}
		}
	}
	
	printf("%d", cost);
	
	return 0;
	
}

1. Prim Algorithm : 크루스칼 알고리즘과 마찬가지로 MST, 즉 최소 비용 신장 트리를 구현하기 위한 알고리즘이다. 다른 점은 프림 알고리즘은 노드를 기준으로 점차 확장해가는 느낌이다. 그렇기 때문에 사이클이 생기는지 확인할 필요가 없다.

 

• 임의의 노드를 선택한다. 나는 여기서 1로 시작하겠다.
  • 어떤 지점으로부터 1로 왔다고 가정한 것이기 때문에 pQ.push(Edge(1,0)) 으로 시작한다.
  • 1과 연결되어있는 노드는 각각 2와 9이며 가중치는 12, 25이다. 이는 인접리스트인 V[1]에 할당되어있다.
  • 2와 9에서도 1로 갈 수 있기 때문에 무방향 그래프이다.
  • 우선순위큐 pQ에는 현재 Edge(1, 0)이 들어있다. while() 문을 순회한다.
    1. Edge temp = pQ.top()
       • temp = Edge(1, 0)
       • _node = 1, _cost = 0
    2. ch[1] == 0, 즉 1을 한 번도 연결하지 않았다.
       • ch[1] = 1 (연결했음을 의미)
       • cost += _cost (연결했기 때문에 가중치 더하기)
       • V[1] 에는 (2, 12), (9, 25)가 있다. 그것들을 각각 pQ.push() 한다.
• 우선순위큐 pQ에는 (2, 12), (9, 25)가 있다. 최소힙이기 때문에 pQ.top()은 (2, 12)가 된다. (가중치 기준)
  • 위와 같이 반복한다.

 

 

https://kbw1101.tistory.com/52

[알고리즘] 프림(Prim) 알고리즘으로 MST 찾기 (C++로 구현하기)

https://ansohxxn.github.io/algorithm/mst/

(C++) 최소 신장 트리 MST, 크루스칼 알고리즘, 프림 알고리즘