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

문제 링크

섬 연결하기

풀이

최소 신장 트리 문제. 나는 크루스칼 알고리즘으로 풀었다.

1. 먼저 costs를 compare함수를 통해 비용 순으로 오름차순 정렬을 했다.
2. parent는 각 인덱스의 부모 노드의 인덱스가 들어가게 된다.
3. getParent 함수는 그 노드의 부모 노드 인덱스가 반환된다.
   3-1. unionParent 함수는 부모 노드를 합치는 것으로 작은 값으로 합친다.
   이는 노드 두 개가 연결된 것을 의미한다.
   3-2. find 함수는 부모가 같은지 확인하는 것으로, 최소 신장 트리는 사이클이 생기면 안되는데, 부모 노드가 같은지 확인하는 과정을 통해 사이클이 있는지 없는지 알 수 있다.
4. costs를 반복문으로 돌리면서 find 함수를 통해 true면 노드를 잇지 않고, false면 노드를 이어 answer에 비용을 추가한다.
   4-1. 노드를 잇기 위해 unionParent를 통해 부모 노드를 합친다.

코드

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

using namespace std;

bool compare(vector<int> a, vector<int> b){
    if(a[2]==b[2]) return a<b;
    else return a[2]<=b[2];
}

int getParent(vector<int> v, int x) //부모 노드 찾기
{
    if(v[x]==x) return x;
    else return v[x] = getParent(v,v[x]);
}

void unionParent(vector<int> &v, int x, int y) //부모 노드 합치기
{
    x = getParent(v,x);
    y = getParent(v,y);
    if(x<y) v[y]=x;
    else v[x]=y;
}

bool find(vector<int> v, int x, int y) //부모가 같은지 확인
{
    x = getParent(v,x);
    y = getParent(v,y);
    if(x==y) return true;
    else return false;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    sort(costs.begin(), costs.end(),compare);
    
    vector<int> parent(n);
    for(int i=0;i<n;i++)
    {
        parent[i]=i;
    }
    
    for(int i=0;i<costs.size();i++)
    {
        if(find(parent, costs[i][0],costs[i][1])) continue;
        answer+=costs[i][2];
        unionParent(parent, costs[i][0], costs[i][1]);
    }
    
    return answer;
}