[프로그래머스 고득점 kit] 섬 연결하기 c++ (mst)

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42861#

프로그래머스

 

문제 해설

이 문제는 " 전체를 연결하는 최소 비용" 에서 MST문제임을 캐치할 수 있다. 

 

MST란?

 union-find 알고리즘을 통해 트리로 구성하여 새롭게 그룹에 참여하는 간선을  비용이 낮은 순으로 Union 해서 최소 비용을 찾는 문제이다. N개의 Vertex가 있다면, N-1 개의 간선을 병합하여 전체를 1개의 그룹으로 만들 수 있다.

정답 코드

#include <string>
#include <vector>
#include<queue>
using namespace std;
int parent[110];
struct edge{
    int a;
    int b;
    int cost;
    bool operator < (edge other)const{
        return cost>other.cost;
    }
};

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

void join(int pa,int pb){
    if(pa!=pb) parent[pa]=pb;
}


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
     priority_queue<edge> pq;//cost, vertex
    for(int i=0;i<=n;i++) parent[i]=i;
    for(auto c:costs){
        int a=c[0],b=c[1],cost=c[2];
        pq.push({a,b,cost});
    }
    int cnt=n-1,sum=0;
    while(!pq.empty()){
        edge now=pq.top();
        pq.pop();
      //  printf("%d, %d\n",now.a,now.b);
        int pa=find(now.a),pb=find(now.b);
        if(pa!=pb){
           // printf("join: %d, %d\n",pa,pb);
            join(pa,pb);
            sum+=now.cost;
            cnt--;
            if(cnt<=0){
                return sum;
            }
            
        }
        
    }
   
    return -1;
}