백준 1197 c++

최소신장트리의 가중치 총합을 구하는 문제이다.
MST를 구하기 위해 쿠르스칼 알고리즘을 사용했고 프림알고리즘을 통해서도 해결해 보겠다.
문제풀이중 간선개수가 (노드개수 - 1) 을 만족하면 조기종료하는 방법을 시도해봤는데, 조건을 확인하는 시간이 추가되어 오히려 시간이 늘었다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void input_graph(int *V, int *E, vector<pair<int, pair<int, int>>>&graph)
{
	int i;
	int A, B, C;

	cin >> *V >> *E;
	for (i = 0; i < *E; i++)
	{
		cin >> A >> B >> C;
		graph.push_back({ C, {A, B} });
	}
	sort(graph.begin(), graph.end());//가중치 기준으로 정렬

	return;
}

//부모노드 찾는 함수
int get_parent(vector <int>& parent, int x)
{
	if (parent[x] == x)
	{
		return x;
	}
	else
	{
		return parent[x] = get_parent(parent, parent[x]);
	}
}

//두 부모노드를 합치는 함수
void union_parent(vector <int>& parent, int a, int b)
{
	a = get_parent(parent, a);
	b = get_parent(parent, b);

	//더 작은 값으로 부모를 저장한다.
	if (a < b)
	{
		parent[b] = a;
	}
	else
	{
		parent[a] = b;
	}
}

//같은 부모를 가지는지 확인하는 함수 == 같은 그래프에 속해 있는지 확인
bool find_parent(vector <int>& parent, int a, int b)
{
	a = get_parent(parent, a);
	b = get_parent(parent, b);

	if (a == b)//같은 부모라면
	{
		return true;
	}
	else//다른 부모라면
	{
		return false;
	}
}

int find_answer(int V, int E, vector<pair<int, pair<int, int>>>& graph)
{
	//최소신장트리 MST를 구하는 방법
	//브루트포스 : 비효율
	//그리디알고리즘
	//프림알고리즘(다익스트라 알고리즘은 프림알고리즘과 비슷하지만, 가중치가 음수면 사용 불가능하다)
	//쿠르스칼알고리즘
	//MST의 간선개수는 모든 노드 개수 -1

	//쿠르스칼 알고리즘을 사용해 볼것이다.
	//1. 가중치 순으로 오름차순 정렬된 자료
	//2. find
	//3. union
	
	vector <int> parent(V + 1);
	int i;
	int min_sum = 0;
	int edge_count = 0;

	//기본적으로 모든 노드가 자기자신을 부모로 지정하도록 초기화
	for (i = 0; i < V + 1; i++)
	{
		parent[i] = i;
	}
	for (i = 0; i < graph.size(); i++)//저장된 자료에 대해 모두 순회
	{
		//사이클이 발생하지 않는 경우 그래프에 포함
		if (!find_parent(parent, graph[i].second.first, graph[i].second.second))//두점에 대해 parent가 같지 않다면
		{
			min_sum += graph[i].first;
			union_parent(parent, graph[i].second.first, graph[i].second.second);//두점의 부모를 작은 부모노드값으로 저장
			edge_count++;
		}
		//그런데 만약....최소비용 신장트리의 간선 개수는 모든 노드개수 -1이니까 그 값에 도달하면 정지한다고 하면... 시간이 줄어들을까?
		//if문을 확인하는 시간이 추가됨
		if (edge_count == V - 1)
		{
			break;
		}
	}

	/*
	i = 0;
	while (edge_count != V - 1 || i != graph.size())
	{
		//사이클이 발생하지 않는 경우 그래프에 포함
		if (!find_parent(parent, graph[i].second.first, graph[i].second.second))//두점에 대해 parent가 같지 않다면
		{
			min_sum += graph[i].first;
			union_parent(parent, graph[i].second.first, graph[i].second.second);//두점의 부모를 작은 부모노드값으로 저장
			edge_count++;
		}
		i++;
	}
	*/

	return min_sum;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int V, E;
	vector<pair<int, pair<int, int>>>graph;//(가중치, (시작점, 끝점))

	input_graph(&V, &E, graph);
	cout << find_answer(V, E, graph) << "\n";

	return 0;
}