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

문제

---

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

풀이

---

노드 간 연결 비용을 최소로 하여 모든 노드와 연결해야하는 문제로, 크루스칼 알고리즘을 통해 해결하였다. 크루스칼 알고리즘은 최소 신장 트리를 구하는 알고리즘으로, 가중치의 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택합니다.

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

using namespace std;

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

int getRoot(vector<int>& parent, int x) 
{
    if (parent[x] == x) return x;
    return parent[x] = getRoot(parent, parent[x]);
}

void unionParent(vector<int>& parent, int a, int b)  
{
    int par_a = getRoot(parent, a);
    int par_b = getRoot(parent, b);
    if (par_a < par_b) parent[par_b] = par_a;
    else parent[par_a] = par_b;
}

bool find(vector<int>& parent, int a, int b) 
{
    int par_a = getRoot(parent, a);
    int par_b = getRoot(parent, b);
    if (par_a == par_b) return true;
    else return false;
}

int solution(int n, vector<vector<int>> costs) 
{
    int answer = 0;
    bool island[101] = { false };
    vector<int> parent_node(n);
    //비용 순으로 오름차순 정렬
    sort(costs.begin(), costs.end(), cmp);

    for (int i = 0; i < parent_node.size(); i++)
    {
        parent_node[i] = i;
    }
    
    for (int i = 0; i < costs.size(); i++)
    {
        if (!find(parent_node, costs[i][0], costs[i][1]))
        {
            unionParent(parent_node, costs[i][0], costs[i][1]);
            answer += costs[i][2];
        }
    }

    return answer;
}