https://www.acmicpc.net/problem/1197
문제 요약
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성해야합니다..
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말합니다.
첫째 줄에 정점의 개수 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. 부모 배열을 정점의 사이즈로 만들어 각자 자기 인덱스를 넣습니다. ( 모든 정점의 초기 부모는 자기 자신 )
2. 그래프트는 크루스칼 일고리즘 사용을 위해 가중치 기준으로 받습니다.
3. 가중치 기준으로 받은 그래프를 정렬합니다.
4. 최소신장트리를 만들기 위해 탐색합니다. 가중치 기준으로 정렬했기 때문에 첫번째 정점이 가장 작은 가중치를 가진 정점입니다.
5. 정점과 연결된 정점을 각각 부모 탐색 함수를 돌립니다. 부모 탐색 함수 내에서는 현재 정점과 현재 정점의 부모가 같으면 반환하고 아닐경우에는 현재 정점의 부모를 부모 탐색 함수를 재귀 호출합니다. ( 최종 부모 찾는 중 )
6. 그렇게 찾은 두개의 부모를 변수에 저장하고 비교합니다. 둘이 같지 않을경우에 ( 부모가 같지 않다는건 현재 최소 신장 트리에 속해 있지 않다는 것 ) 두번째 정점의 부모의 부모를 첫번째 정점의 부모로 최신화합니다.
7. 그리고 현재 가중치를 더합니다.
8. 탐색을 마치면 더해진 가중치를 출력합니다.
주의할 점
크루스칼 알고리즘은 가중치 기준으로
코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, pair<int, int>>>v;
int p[10004];
int n, m;
int sum = 0;
int findParent(int v)
{
// 현재 정점과 부모가 같지 않은 경우
if (p[v] != v)
{
// 부모의 부모를 찾아 떠남
p[v] = findParent(p[v]);
}
// 현재 v와 부모가 같아진 경우 ( 최소 가중치 ) 반환
return p[v];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
// 부모 배열 초기화
for (int i = 1; i <= n; i++)
{
p[i] = i;
}
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
// 가중치 기준으로 벡터 받음
v.push_back({ c, {a, b} });
}
// 가중치 기준으로 정렬
sort(v.begin(), v.end());
for (int i = 0; i < m; i++)
{
// 정렬된 가중치 순으로 간선이 연결되어 있는 정점의 부모를 최신화
int Aparent = findParent(v[i].second.first);
int Bparent = findParent(v[i].second.second);
// 같은 부모일 경우는 이미 연결된 경우
if (Aparent != Bparent)
{
// 뒤에 정점 부모의 부모를 현재 정점의 부모로 초기화
p[Bparent] = Aparent;
// 연결된 선은 가중치를 더함
sum += v[i].first;
}
}
// 가중치 총합 출력
cout << sum;
return 0;
}예제
3 3
1 2 1
2 3 2
1 3 3결과
