https://www.acmicpc.net/problem/1197

해결방법

최소신장트리를 잘 구현만 하면 되는 문제..인데
스드스 특강때 했던거 까먹어서 ㅎㅎ 다시 정리했다

최소신장트리?

Minimum Spanning Tree / MST : 최소 “비용” 신장트리
무향 연결 가중 그래프 G에서 간선의 가중치의 합이 최소인 신장 트리
⇒ 통신 네트워크나 빠른 길찾기 문제에서 활용된다고 함!
    ex. 모든 지점을 연결하되, 연결선의 총 길이가 최소가 되어야 하는 문제

구현방법

• 크루스칼
• 프림
• 솔린

MST를 구하는 알고리즘 세 개 중에서, 크루스칼 알고리즘을 사용했다.

크루스칼 알고리즘

Greedy알고리즘의 일종으로,
간선들을 가중치 오름차순으로 정렬 + 사이클을 형성하지 않는 선 에서 순서대로 간선 선택
시간복잡도는 $O(E\log V)$

[사이클 판별하는 법]

Union-Find를 이용한다.
만약 부모가 같다 ⇒ 사이클을 형성하므로, Union 연산을 하지 않고 선택도 안함
만약 부모가 다르다 ⇒ 사이클을 형성하지 않으므로, Union 연산 + 선택

[알고리즘 동작과정]

• 모든 edge를 가지는 집합 S를 만든다.
• S를 가중치 순서대로 정렬한다.(작은 순서대로)
• 하나씩 뽑아서 해당 간선을 추가했을 때 사이클을 형성하는지 판별한다. (by Union-Find)
  • 부모가 같다면(사이클 존재), pass
  • 부모가 다르다면(사이클 X), Union연산 + 선택

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long

const int v_ = 10001;
const int e_ = 100001;
int parent[v_];
vector<pair<ll,pair<int,int>>> edges;

int V,E;

int find(int n){
	if(parent[n]==n) return n;
	return find(parent[n]);
}

void uni(int a, int b){
	a = find(a);
	b = find(b);
	if(a==b) return;
	if(a>b) swap(a,b);
	parent[b] = a;
}

bool isCycle(int a, int b){
	a = find(a);
	b = find(b);
	return (a==b);
}

ll solve(){
	ll answer = 0;
	for(int i = 0; i<=V; i++)
		parent[i] = i;
	for(int i = 0; i<E; i++){
		if(!isCycle(edges[i].second.first,edges[i].second.second)){
			uni(edges[i].second.first, edges[i].second.second);
			answer += edges[i].first;
		}
	}
	return answer;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin>>V>>E;
	for(int i = 0; i<E; i++){
		ll a,b,c; cin>>a>>b>>c;
		edges.push_back({c,{a,b}});
	}
	sort(edges.begin(),edges.end());
	cout<<solve();
}

제출결과

참고

https://ko.wikipedia.org/wiki/크러스컬_알고리즘
https://chanhuiseok.github.io/posts/algo-33/