22.7.16

78. 원더랜드(Kruskal MST 알고리즘 : Union&Find 활용)

문제를 풀다가 감이 잘 안 잡혀서 Kruskal 알고리즘에 대해 찾아보았다.
크루스칼 알고리즘은 이 문제에서 요구하는 바 그 자체이다.
그래프가 있을 때 그래프에서 모든 정점을 포함하고, 사이클이 생성되지 않는 그래프를 신장트리라고 하는데, 이 신장트리중 연결된 부분의 가중치의 합이 최소가 되도록 구성한 그래프를 최소신장트리라고 한다.
이 최소신장트리를 구하기 위한 알고리즘이 크루스칼 알고리즘이다.

int main(){
	
	//freopen("input.txt","rt",stdin);

	int k, e, a, b, c;
	cin>>k>>e;
	for(int i=1; i<k; i++){
		unf[i]=i;
	}
	for(int i=0; i<e; i++){
		cin>>a>>b>>c;
		v.push_back(Data(a,b,c));
	}
	sort(v.begin(), v.end());
	
	int answer, x, y;
	for(int i=0; i<v.size(); i++){
		x = v[i].n1;
		y = v[i].n2;
		
		if(find(x)!=find(y)){
			Union(x,y);
			answer+=v[i].cost;	
		}
	}
	cout<<answer;
	
	return 0;

}

Data 는 첫번째, 두번째 도시 번호와 간선의 비용을 포함한 구조체이다.

알고리즘의 원리는 알았는데, 도대체 cycle을 구성하는지 아닌지를 어떻게 판별해야하는지를 생각하는데에 시간을 많이 썼다.. 생각해보면 정말 간단했는데, 사이클이라는 단어에 집중하다보니 너무 복잡하게 생각했다.
그냥 union을 호출하기 전에 이미 같은 집합에 속해있다면, 호출후에는 cycle을 형성하게 되는 것이다.
과연 비슷한 문제에 응용할 수 있을지는 의문이지만 kruscal 알고리즘에 대해 배울 수 있었다.