최소 비용 신장 트리 , 섬연결하기

https://mjmjmj98.tistory.com/75

[알고리즘] MST(Minimum Spanning Tree, 최소 신장 트리) - Prim(프림), Kruskal(크루스칼) 알고리즘

https://mjmjmj98.tistory.com/76

[프로그래머스 / C++] 섬 연결하기

 

출처:

 

위에서는 크루스칼 이론으로 만들었기 때문에 프림 알고리즘으로 구현해 보겠다.

Prim's Algorithm

프림 알고리즘은 Tree에 포함되지 않은 정점들 가운데, 이미 포함된 정점과 가장 가까운 정점을 선택해서 해당 간선을 추가하는 방식이다. 

 

V : 그래프의 모든 정점들의 집합

F : MST에 포함된 간선들의 집합

Y : MST에 포함된 정점들의 집합, Y = V가 되면 MST를 구현한 것

 

첫 번째 정점을 v1이라고 하면 F = { }, Y = { v1 }으로 초기화해준다. 이는 아직 선택된 간선이 없고, v1부터 알고리즘을 수행한다는 의미이다. 

 

Y=V가 될 때까지 다음 과정을 반복한다. 

1. (V - Y)의 정점들 중 Y와 가장 가까운 정점 A를 선택한다. ( weight 가 가장 적은 정점 선택 )
2. Y에 정점 A를 추가한다. 
3. F에 간선을 추가한다. 

 

Y=V가 되어서 MST가 완성되면 F는 MST의 모든 간선을 포함한 집합이 되므로 F의 원소 개수는 (n-1)개가 된다. 

출처: https://mjmjmj98.tistory.com/75 [Live passionate😎]

 

 

 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;



bool isfullnode(int Num, vector<int> node)
{

	for (int i = 0; i < Num; i++)
	{
		if (find(node.begin(), node.end(), i) == node.end()) // 못찾으면 
			return false;
	}
	return true;
}

int main()
{

	int n = 4;
	vector<vector<int>> costs({ {0, 1, 1}, {0, 2, 2}, {1, 2, 5}, {1, 3, 1}, {2, 3, 8} });


	vector<vector<int>> truck;
	vector<int> node;

	node.emplace_back(0); // 시작 노드는 무조건 0;

	while (!isfullnode(n, node))		
	{
		vector<int> temp;
		auto it_temp = costs.end();
		// 노드와 연결된 간선 중에서 제일 weight 가 적은 간선을 선택
		for (auto it_node = node.begin(); it_node != node.end(); it_node++)
		{
			for (auto it_costs = costs.begin(); it_costs != costs.end(); it_costs++)
			{
				if ((*it_costs)[0] == *it_node )  // node 와 연결된 간선 찾기
				{
					if (costs.end() == it_temp)//  제일 처음 값 간선 처리
					{
						it_temp = it_costs;
					}
					else
					{
						if (find(node.begin(),node.end(),(*it_costs)[1]) == node.end()) // 현제 node 에 추가 되어있지 않다면
						{
							if ((*it_costs)[2] < (*it_temp)[2])
								it_temp = it_costs;
						}
						else
						{
							continue;
						} 						
					}

				}
				else if ((*it_costs)[1] == *it_node)
				{
					if (costs.end() == it_temp)//  제일 처음 값 간선 처리
					{
						it_temp = it_costs;
					}
					else
					{
						if (find(node.begin(), node.end(), (*it_costs)[0]) == node.end()) // 현제 node 에 추가 되어있지 않다면
						{
							if ((*it_costs)[2] < (*it_temp)[2])
								it_temp = it_costs;
						}
						else
						{
							continue;
						}

					}
				}
			}
		}

		truck.emplace_back(*it_temp);
		node.emplace_back((*it_temp)[0]);// 중복 되게 넣어 줘도 된다. 즉 노드가 2개씩 들어간다고 생각  
		node.emplace_back((*it_temp)[1]);
		costs.erase(it_temp);
	}

	for (auto it = truck.begin(); it != truck.end(); it++)
	{
		cout << (*it)[0] << ',' << (*it)[1] << ',' << (*it)[2] << endl;
	}

	return 0;
}