[프로그래머스]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 라는 boolean 전역 변수는 간선이 싸이클을 이루는지 아닌지를 가리고
• b 를 체크해서 그래프를 형성하고 가중치를 정립한다.