1922 네트워크 연결 (kruskal 알고리즘)

네트워크 연결 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	10520	5704	3321	52.672%

문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

크루스칼 알고리즘도 MST 알고리즘의 일종입니다.

앞의 prim알고리즘을 푼것에 이어서, 같은 문제를 kruskal알고리즘으로 풀어보도록 하겠습니다.

kruskal알고리즘은 이전에 포스팅한 union find를 사용합니다.

union find를 간단히 설명하자면, 트리를 합치는데,

합치려는 노드들(A,B)이 각자 속한 트리의 root노드를 탐색하여, 같은 root노드면 ( A'root == B's root )

같은 트리내에 있으므로 추가하지 않고 (추가하면 cycle), 다를 때만, 

조건에맞는 (A)root노드를 다른 (B)root노드의 자식으로 놓아서 같은 트리를 만들어줍니다.

코드를 보도록 하겠습니다.

#include <iostream>

#include <cstdlib>

#include <algorithm>

using namespace std;

struct edge{

int start;

int dest;

int cost;

edge(int a,int b,int c):start(a),dest(b),cost(c){} //구조체 생성자

edge(){} // 오버로딩용 안하면 edge E[1001] 에러

};

bool compare_edge(const edge& E1, const edge& E2);

int getParent(int parent[], int a);

void makeUnion(int parent[], int a, int b);

int main(){

freopen("input.txt","r",stdin);

int n,m;

cin>>n>>m;

edge E[100001]; // 간선을 저장할 배열

int parent[1001]; // 각 노드의 부모노드의 번호를 저장할 것입니다.

int min_cost=0; // 최종 최소비용이 되겠습니다.

for(int i=1; i<=n; ++i){ //부모값의 초기값은 자기 자신임.

parent[i] = i;

}

/*간선 값 초기화 (무방향 그래프) */

//간선은 인덱스 0부터 시작해서 저장할 것임.

int s,d,c;

for(int i=0; i<m ;++i){

cin>>s>>d>>c;

E[i] = edge(s,d,c);

}

/*간선 오름차순으로 정렬*/

sort(E,E+m,compare_edge);

// for(int i=0; i<m; ++i){ //간선 한번 출력해보기

// cout<<E[i].cost<<" ";

// }

/*간선들 중 가장 작은 값을 선택한다. 오름 차순이므로 차레대로 탐색*/

for(int edge_number=0; edge_number<m; ++edge_number){

/*선택한 간선을 추가하면 지금 선택된 트리에서 cycle을 형성하는지 체크한다.*/

if( getParent(parent, E[edge_number].start)

!= getParent(parent, E[edge_number].dest)

){ //만약에 간선에 포함된 노드 2개가 같은 트리에 있으면 cycle 이므로 추가하면 안됨. 달라야 추가!

makeUnion(parent,E[edge_number].start,E[edge_number].dest); //같은 트리로 만든다 ㅋ

min_cost += E[edge_number].cost; //추가한 간선의 비용을 추가한다.

// cout<<E[edge_number].cost<<"\n";

// for(int i=1; i<=n; ++i){

// cout<<parent[i]<<" ";

// }

// cout<<"\n";

}

}

//cout<<"\n";

cout<<min_cost;

return 0;

}

/*구조체 edge의 정렬용입니다.*/

bool compare_edge(const edge& E1, const edge& E2){

if( E1.cost < E2.cost ){

return true;

} else {

return false;

}

}

/*유니온 파인드 구현입니다.*/

void makeUnion(int parent[], int a, int b){ //a,b를 union 합니다.

// a,b중 더 부모의 노드번호가 작은것을 부모로하도록 정의하겠습니다.

// 각 트리의 최상의 노드끼리 부모-자식관계를 맺으면 트리가 하나로 합쳐짐을 이용

a=getParent(parent,a); //

b= getParent(parent,b);

if( a>b ) parent[a] = b;

else parent[b] = a;

}

int getParent(int parent[], int a){ //a의 최종부모를 찾습니다.

if( parent[a] == a ) return a; //부모가 자기자신이면 최종 부모입니다. (=root node)

else{

return getParent(parent, parent[a]); //a의 부모에 대해서 재귀적으로 탐색합니다. (그 트리의 root node를 찾을때까지)

}

}