C++:: 프로그래머스 < 섬 연결하기 >

말그대로 섬을 연결하는 최소 비용을 구하면 되는 문제이다. 핵심은 최소 비용의 다리들을 연결하되 연결하고자하는 섬들이 이미 이어져있다면 넘겨야한다는 점이다.

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

bool is_done = false;

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

bool isConnected(int s, int e, int n, vector<vector<int>>& nodes) {// 두섬이 이어져있는지
    vector<bool> vis(n, false);
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (auto& next : nodes[cur]) {
            if (vis[next]) continue;
            vis[next] = true;
            q.push(next);
        }
    }
    if (find(vis.begin(), vis.end(), false) == vis.end()) is_done = true;// 모든 섬이 이어져 있다면
    if (vis[s] && vis[e]) return true;// 두섬이 이어져있다면
    return false;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<vector<int>> nodes(n);
    sort(costs.begin(), costs.end(), compare);// 다리 건설 비용으로 정렬
    for (auto& c : costs) {
        if (is_done) break;
        if (isConnected(c[0], c[1], n, nodes)) continue;
        nodes[c[0]].push_back(c[1]);
        nodes[c[1]].push_back(c[0]);
        answer += c[2];
    }
    return answer;
}