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

프로그래머스

 

• 3 단계에서 처음 본 최소 신장 트리 문제
• 크루스칼 알고리즘을 통해 해결

 

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

using namespace std;

// 최소의 비용으로 모든 노드를 연결해야함 > 크루스칼 알고리즘
// 일단 비용 기준으로 정렬 필요
// 이후 부모 노드를 저장한 뒤 노드들을 순회하며 부모 노드가 같은 경우 = 싸이클이 발생하는 경우를 제외하고 다리를 건설

vector<int> parent(101);

// 부모 노드를 찾는 함수
int FindParent(int x) {
    if(parent[x] == x) return x;
    else return parent[x] = FindParent(parent[x]);
}

// 비교자
int cmp(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 비용 기준으로 정렬
    sort(costs.begin(), costs.end(), cmp);
    
    // 부모 노드 저장
    for(int i = 0; i < n; i++)
        parent[i] = i;
    
    for(int i = 0; i < costs.size(); i++) {
        int startNode = FindParent(costs[i][0]);
        int endNode = FindParent(costs[i][1]);
        int cost = costs[i][2];
        
        // 부모 노드가 같지 않다면 싸이클이 생기지 않으므로 다리를 건설 및 부모 노드 갱신
        if(startNode != endNode) {
            answer += cost;
            parent[endNode] = startNode;
        }
    }
    
    return answer;
}