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

programmers.co.kr/learn/courses/30/lessons/42861#

코딩테스트 연습 - 섬 연결하기

후기

1. 유니온 파인드, 크루스칼 처음 써봤는데 진짜 개꿀인거같다. 더 연습해야징

 

풀이

1. 유니온 파인드 함수들 미리 만들어 둔다

1) getParent

: 재귀함수로 루트 찾기, 루트는 젤 작은 숫자로 할거임

 

2) connect

: 부모를 통일시키면 사실상 연결된거

: 아까 위에서 말했듯이 작은 숫자가 루트니까 둘중 더 작은 부모로 통일 시킴

2. 미리 가격 싼순으로 sort 해둔다!

#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 getParent(int x)
{
    if(parent[x]==x)
        return x;
    return parent[x]= getParent(parent[x]);
}

void connect(int x, int y)
{
    x = getParent(x);
    y = getParent(y);
    if(x<y)
        parent[y]=x;
    else
        parent[x]=y;
}

bool find(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    return a == b;
}

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(!find(costs[i][0],costs[i][1]))//연결이 안되있는 상태면
        {
            connect(costs[i][0],costs[i][1]);
            answer += costs[i][2];
        }
    }
    
    return answer;
}