[프로그래머스] 섬 연결하기(C++)

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

프로그래머스

처음에는 visit 벡터를 두고, cost가 작은 순대로 정렬해둔 costs 벡터를 차례로 조회하며

다 방문하면 끝나게끔 코드를 짰다.

그러나 그럴 경우, 0부터 3까지의 섬이 있다고 가정했을 때

[0,1,1], [2,3,1]까지만 조회해도 끝난다. 1과 2가 연결되지 않았음에도!

 

크루스칼 알고리즘을 활용하면 최소신장트리(MST)를 만들 수 있다.

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

vector<int>parent;

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

int find_parent(int i)
{
    if(i==parent[i]) return i;
    return find_parent(parent[i]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(),costs.end(),cmp);//cost 기준 정렬
    
    parent=vector<int>(n);
    for(int i=0;i<n;i++)
        parent[i]=i;
    
    for(int i=0;i<costs.size();i++)
    {
        int a=costs[i][0];//첫번째 섬
        int b=costs[i][1];//두번째 섬
        if(find_parent(a)!=find_parent(b))
        {
            a=find_parent(a);
            b=find_parent(b);
            //작은 숫자가 부모가 되도록
            if(a<b)
                parent[b]=a;
            else
                parent[a]=b;
            answer+=costs[i][2];
        }
    }
    
    return answer;
}