프로그래머스 섬연결하기 - C++

문제 설명

이번 MST문제는 크루스칼 알고리즘을 사용하여 풀었다.
크루스칼 알고리즘은 최소신장트리를 만들때 사용하는 알고리즘 하나로, 최소 비용의 간선을 오름차순으로 정렬 한 후, 정렬된 간선을 하나씩 하나씩 확인하면서 현재 간선이 노드들간의 싸이클을 발생시키지 않는것만 연결하여 최소신장트리를 만드는 알고리즘이다.

문제 풀이

1. 부모노드들을 자기 자신으로 초기화해주기
2. 간선을 간선의 비용이 오름차순이 되도록 정렬해주기
3. 정렬된 간선이 하나씩 확인하며 싸이클이 있는지 확인
4. 싸이클이 없으면 최소신장트리에 포함 시키기
5. 간선의 갯수 만큼 반복

소스코드

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

using namespace std;

int parent[101];                            // 부모

bool cmp(vector<int> a, vector<int> b)      // 정렬할 때 조건 넣기용 함수
{
    return a[2] < b[2];
}

    int findparent(int a)                   // 부모 찾기 함수
    {
        if (parent[a] == a) return parent[a];
        return parent[a] = findparent(parent[a]);
    }

    void unionparent(int a, int b)          // 결합하는 함수
    {
        a = findparent(a);
        b = findparent(b);
        if (b > a)
            parent[b] = a;
        else if (b < a)
            parent[a] = b;
    }
    bool sameparent(int a, int b)           // 싸이클 유무가있는지 확인하는 함수
    {
        if (findparent(a) == findparent(b))
            return true;
        return false;
    }

int solution(int n, vector<vector<int> > costs)     
{
    int answer = 0;
    for (int i = 0; i < n; i++)                 // 초기화
        parent[i] = i;
    sort(costs.begin(),costs.end(),cmp);        // 비용이 낮은순으로 정렬하기
    for (int i = 0; i < costs.size(); i++)
    {
        if (!sameparent(costs[i][0],costs[i][1]))   // 싸이클이 없으면 연결해주기
        {
            unionparent(costs[i][0],costs[i][1]);
            answer+= costs[i][2];
        }
    }
    return answer;
}