섬 연결하기 - 크루스칼 알고리즘

크루스칼 알고리즘 

 

spanning tree

- 신장 트리 , 그래프내의 모든 정점을 포함하는 트리로 그래프의 최소 연결 부분 그래프이다. 

- n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1 개이다. 

 

minimum spanning tree

- 가장 적은 비용으로 모든 노드를 연결하는 것으로 이 때 사용하는 알고리즘 중 하나가 크루스칼 알고리즘이다

 

알고리즘 진행 순서

1. 비용을 기준으로 오름차순으로 정렬

2. 정렬된 순서에 맞게 그래프에 포함

3. 포함시키기 전에 사이클 테이블을 확인한다. -> 이때 사이클을 확인하는 방법이 Union Find (합집합 찾기, 서로소집합 알고리즘)

4. 사이클을 형성하는 경우 간선을 포함하지 않는다. 

 

 

참고: m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https:%2F%2Fwww.google.com%2F

18. 크루스칼 알고리즘(Kruskal Algorithm)

 

<문제>

programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

bool compare(vector<int>a, vector<int>b){
    return a[2]<b[2];
}

int getparent(vector<int>&parent,int i){
    if(parent[i]==i){return i;}
    return parent[i]=getparent(parent,parent[i]);
}

void unionparent(vector<int>&parent, int i, int j){
   i = getparent(parent,i);
   j = getparent(parent,j);
    if(i<j){parent[j]=i;}
    else{parent[i]=j;}
}

int find(vector<int>&parent, int i, int j){
    i = getparent(parent,i);
    j = getparent(parent,j);
    if(i==j)return 1;
    else{ return 0;}

}



int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<int>parent(n);
    
    sort(costs.begin(),costs.end(),compare);
    
    for(int i=0; i<n; i++){
        parent[i]=i;
    }
    
    for(int i=0; i<costs.size(); i++){
     //   cout<<costs[i][2]<<" ";
      if(!find(parent,costs[i][0],costs[i][1])){
          answer +=costs[i][2];
          unionparent(parent,costs[i][0],costs[i][1]);
      }
        
    }
    
    return answer;
}