백준 1197번 최소 스패닝 트리

문제

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

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

입력

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

최소 스패닝 트리의 가중치가 -2147483648보다 크거나 같고, 2147483647보다 작거나 같은 데이터만 입력으로 주어진다.

 

 

 

크루스칼 알고리즘 구현.

우선 입력 받는 두 정점과 가중치에  대한 정보가 들어오게 되고 

이 정점과 관계없이 가중치에 대해서 먼저 정렬이 필요하다.

따라서 정점의 정보와 가중치의 정보가 함께 움직이면서 가중치에 정보에 대해서만 정렬을 해야 하는데

이를 위해 Struct형태의 구조를 짜고 객체형 벡터를 선언해 주었다.

벡터를 sort하는데 있어서 기준이 되는 값은 weight이므로 내부 연산자 오버로딩을 통해 sort의 기준을 정해 주었다.

그 다음 부터는 들어오는 두 정점은 각 객체를 담는 벡터에 저장되어야 하고 이후 sort에 의해 내림차순으로 정렬된다.

가장 앞에 있는 객체가 가장 큰 weight를 가지고 있으므로 앞에서 부터 두 정점을 이어 주면 되는데 기준은 같은 트리에 속하면 안된다는 것이다. 이 기준은 부모가 같은지에 따라 결정되므로, 객체의 두 정점의 부모를 불러와서 비교한 후에 값이 다른 경우에 한해서 merge 시키면서 result변수에 weight값을 누적해 주었다.

부모를 찾는 방식은 부모가 자신과 같으면 그대로 반환이고 아니면 부모 노드에 대해 재귀 시키면서 올라가면 되는데 이는 트리의 길이만큼 시간이 걸리므로 자신의 부모를 업데이트 시키는 과정을 포함한다. 따라서 자기의 바로 윗 노드는 집합의 루트이고 2단계 트리를 만족시키게 된다. 

merge하는과정도 중요한데, merge를 수행함으로써 부모가 바뀌기 때문이다. 부모의 정보로 weight가 더해질지 결정 되므로 merge 의 조건도 잘따져야 한다. merge는 기본적으로 사이즈가 작은것이 큰것에 속하도록 구성된다.

 

모든 알고리즘에 있어서 두 정점이 연결된다 합쳐진다라고 하면 merge가 반드시 필요하고 마구잡이 연결이 아닌 같은 트리에 대한 연결을 지양한다고 하면 parent를 비교하는 작업이 꼭 필요하다.

 

객체형 벡터에 대해서 연산자 오버로딩을 통해 sort시키는 방법 잘 기억해두자.  

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int parent[100000];
int size[100000];

int findparent(int Node)
{
if(parent[Node]==Node)
return Node;


return parent[Node]=findparent(parent[Node]);


}

void merge(int A, int B)
{   
   
    int node1=findparent(A);
    int node2=findparent(B);
    
       if (size[node1] < size[node2])
       {
  
       
         parent[node1] = node2; //node2 집합이 node1에 합쳐짐

            size[node2] += size[node1]; //node1의 집합 크기가 커짐

            size[node1] = 0; 

           }
      else if(size[node1]>=size[node2])
      {
       parent[node2] = node1; //node2 집합이 node1에 합쳐짐

            size[node1] += size[node2]; //node1의 집합 크기가 커짐

            size[node2] = 0; 
      
  }


}

struct Node{

int x;
int y;
int weight;

bool operator<(Node const &e)
{

return weight < e.weight;

}

};

int main(void)
{


 int V,E;
 
 cin >> V >> E;
 

    vector edge;
    
 for(int i=0 ; i <E; i++)
 {
  int a, b, c;
  cin >> a >> b >> c;
 
 edge.push_back({a,b,c});
 }
 
 
 for(int i=0 ; i<V; i++)
 {
  parent[i]=i;
  size[i]=1;
 
 }
 

  sort(edge.begin(),edge.end());
 
 
 int result=0;
 
  for(int j=0; j<edge.size(); j++)
  {
  if(findparent(edge[j].x)!=findparent(edge[j].y))
  {
  merge(edge[j].x,edge[j].y);
  result +=  edge[j].weight;
 
 }
 
 }
 
 cout << result;
 
 


}