[프로그래머스] 섬연결하기

klean·2021년 3월 19일
0

문제

그래프가 주어집니다(vertex 수, 엣지 리스트). 가장 적은 비용으로 모든 노드를 연결하는 경우의 cost를 구하세요.

아이디어

MST 문제였다. MST는 프림 알고리즘과 크루스칼 알고리즘으로 풀수 있는데 문제 카테고리가 그리디여서 크루스칼로 풀게 되었다.

크루스칼 알고리즘

비용이 작은 노드 순으로 합칠 수 있는지 검사를 하자!

합칠 수 있는지 검사를 하는 방법은 Union-Find를 쓰면 된다.
가장 간단한 Union - Find는 하나의 1차원 배열에 이 노드의 부모/혹은 조상/혹은 root를 저장하는 방법이다.

코드

나동빈님의 크루스칼 알고리즘을 참고해 구현했다.
https://m.blog.naver.com/ndb796/221230994142
조금 다른 점이 있다면 엣지를 문제에서 주어진대로 vector 원소가 3개인 걸 사용했고, 이 엣지에 대해 compare 함수를 구현해주었다는 것이다.

#include <string>
#include <vector>
#include<algorithm>
using namespace std;
//minimal spanning tree
int set[100];
int getParent(int set[], int x){
    if(set[x] == x) return x;
    return set[x]=getParent(set,set[x]);
}
void unionParent(int set[], int a, int b){
    a = getParent(set,a);
    b = getParent(set, b);
    if(a<b) set[b] = a;
    else set[a] = b;
}
int find(int set[], int a, int b){
    a = getParent(set, a);
    b = getParent(set, b);
    if(a==b) return 1;
    else return 0;
}
bool comp(vector<int> &a, vector<int> &b){
    return a[2]<b[2];
}
int solution(int n, vector<vector<int>> costs) {
    int sum = 0;
    for(int i = 0;i<n;i++){
        set[i]= i;
    }
    sort(costs.begin(),costs.end(),comp);
    for(int i = 0;i<costs.size();i++){
        if(!find(set, costs[i][0],costs[i][1])){
            sum+=costs[i][2];
            unionParent(set, costs[i][0], costs[i][1]);
        }
    }
    return sum;
}

0개의 댓글