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

크루스칼 알고리즘을 이용하는 문제이다.

처음에 문제를 보고 크루스칼 알고리즘이 떠오르지 않아 헤매다가 구글링을 통해 찾아보며 풀이 방법을 알게 되었다.

 

크루스칼 알고리즘이란?

• 간단하게 설명하면 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다.
• 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 된다.
• 즉 최소 신장 트리를 구하기 위한 알고리즘이다.

 

참고

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

---

다른 풀이 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> island(101);

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

int findParent(int idx){
    if(island[idx]==idx)
        return idx;
    return island[idx]=findParent(island[idx]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for(int i=0; i<n; i++){
        island[i]=i;
    }
    // 비용이 작은 순으로 정렬
    sort(costs.begin(), costs.end(), cmp);
    
    for(int i=0; i<costs.size(); i++){
        int start=findParent(costs[i][0]);
        int end=findParent(costs[i][1]);
        int cost=costs[i][2];
        
        // cycle이 만들어지지 않으면 다리를 추가
        if(start!=end){
            answer+=cost;
            island[end]=start;
        }
    }
    
    return answer;
}

 

https://hyeri0903.tistory.com/199

[프로그래머스] 섬 연결하기 (C++)