[プログラマー]level-3島を接続する(クルーズアルゴリズム)

https://programmers.co.kr/learn/courses/30/lessons/42861


この問題の目的は,各島を接続する最小費用,最小費用成長ツリー(MST)をクルースカアルゴリズムにより得ることである.
「延長ツリー」(Spanning Tree)とは、既存のグラフィック内のすべてのノードを含むが、ループが存在しないグラフィックツリーを意味します.

に道を教える

幹線ごとに昇順に並ぶ(重み付け)

幹線の両端にループが形成されていなければ(dfsを通って一端から一端に到着しなければ)、接続!

サイクルを形成する幹線を採用しない!

マイコード

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

using namespace std;

vector<int> graph[101];
bool check[101] = {false,};
bool b = false;
int to;

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

void dfs (int start) {
    check[start] = true;
    for (int i = 0; i < graph[start].size(); i++) {
        if (to == graph[start][i]) {
            b = true;
            return;
        }
        if (!check[graph[start][i]]) dfs(graph[start][i]);
    }
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    sort(costs.begin(), costs.end(), cmp);
    
    for (int i = 0; i < costs.size(); i++) {
        int start = costs[i][0];
        to = costs[i][1];
        
        memset(check, false, sizeof(check));
        
        dfs(start);
        
        if (!b) {
            graph[start].push_back(to);
            graph[to].push_back(start);
            answer += costs[i][2];
        } else {
            b = false;
        }
    }
    
    return answer;
}

bというブールグローバル変数は、幹線が循環を構成するか否かを判断するために使用され、

.

bを確認し、グラフを形成し、重み付け値を設定します.