[プログラマー]島(C++)への接続

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

vector<int> parents;

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

int getParent(int x) {
    if (parents[x] == x) { return x; }
    return parents[x] = getParent(parents[x]);
}

void unionNodes(int x, int y) {
    x = getParent(x);
    y = getParent(y);
    if (x < y) { parents[y] = x; }
    else { parents[x] = y; }
}

// Solution #1 Kruskal's Algorithm 활용
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    // 부모 노드 담는 벡터 초기화
    for (int i=0; i<n; i++) { parents.push_back(i); }
    
    // 건설 비용이 적은 순으로 정렬
    sort(costs.begin(), costs.end(), cmp); 

    int size = costs.size();
    for (int i=0; i<size; i++) {
        int first = costs[i][0]; // 첫 번째 섬의 번호
        int second = costs[i][1]; // 두 번째 섬의 번호
        
        // 아직 통행이 불가능할 경우 (부모 노드가 다른 경우)
        if (getParent(first) != getParent(second)) {
            unionNodes(first, second); // 다리 건설
            answer += costs[i][2]; // 비용 추가
        }
    }
    
    return answer;
}

#include <string>
#include <vector>
#include <queue>
using namespace std;

struct Node {
    int id; // 섬의 번호
    int cost; // 비용
};

struct Cmp {
    bool operator()(const Node &a, const Node &b) {
        return a.cost > b.cost;
    }
};

vector<bool> visited(100, false);

// Solution #2 Prim's Algorithm 활용
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    priority_queue<Node, vector<Node>, Cmp> minHeap; // 비용이 적은 순으로 정렬되는 최소힙
    minHeap.push({0, 0}); // 0번 섬을 기준으로 탐색 시작
    int size = costs.size();
    while (!minHeap.empty()) {
        Node curNode = minHeap.top();
        minHeap.pop();

        if (visited[curNode.id]) {
            // 이미 방문한 섬일 경우 스킵
            continue;
        }

        visited[curNode.id] = true;
        answer += curNode.cost;

        for (int i=0; i<size; i++) {
            // 인접한 섬들의 번호와 다리 건설 비용 minHeap에 push
            if (costs[i][0] == curNode.id) {
                minHeap.push({costs[i][1], costs[i][2]});
            }
            else if (costs[i][1] == curNode.id) {
                minHeap.push({costs[i][0], costs[i][2]});
            }
        }
    }

    return answer;
}