백준 1197(최소 스패닝 트리) C++

 

최소 스패닝 트리 성공

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

44226

18188

10186

39.911%

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 1 복사

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1 복사

3

 

<코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int parent[10001];
vector<pair<int, pair<int, int>>> edge;
int Find(int x) //루트노드를 찾아주고, 갱신하는 함수
{
	if (parent[x] == x) return x;
	else return parent[x] = Find(parent[x]);
}
void Union(int x, int y) //x,y 서로 루트노드가 다르다면 그 간선을 추가시키는 함수
{
	x = Find(x);
	y = Find(y);
	if (x != y) parent[y] = x;
}
int Same_root(int x, int y) //x,y의 루트노드가 같은지 판단하는 함수
{
	x = Find(x);
	y = Find(y);
	if (x == y) return 1;
	else return 0;
}
int main()
{
	int V, E, res = 0;
	cin >> V >> E;
	for (int i = 0; i < E; i++)
	{
		int A, B, C;
		cin >> A >> B >> C;
		edge.push_back(make_pair(C, make_pair(A, B)));
	}
	sort(edge.begin(), edge.end());//간선들을 가중치를 기준으로 오름차순으로 정렬
	for (int i = 0; i < V; i++)
	{
		parent[i] = i;//처음에는 모든 노드의 부모는 자기 자신으로 초기화
	}
	for (int i = 0; i < E; i++)
	{
		if (Same_root(edge[i].second.first, edge[i].second.second) == 0) //간선의 각 정점의 루트노드가 다르면,
		{
			Union(edge[i].second.first, edge[i].second.second); //간선을 추가하고,
			res += edge[i].first; //그 간선의 가중치를 더한다.
		}
	}
	cout << res;
}

 

<풀이>

크루스칼 알고리즘과 유니온 파인드를 알았어야 하는 문제이다.