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

Pixabay로부터 입수된 angelabeauchamp79님의 이미지 입니다.

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

프로그래머스

 이번 문제는 각 섬들(이하 노드, 노드들)과 이들을 이을 때 드는 비용들이 주어질 때, 모든 노드들을 이을 수 있는 가장 적은 비용을 구하는 문제이다. 이 문제는 딱 보자마자 크루스칼 알고리즘 문제라는 생각이 들었다. 크루스칼 알고리즘이란 가장 적은 비용으로 모든 노드들을 연결할 때 이용할 수 있는 알고리즘이기 때문이다. 즉, 이 문제는 크루스칼 알고리즘의 노드를 섬으로 바꿨을 뿐인 문제이다. 그런데 크루스칼 알고리즘을 이용하기 위해서는 비용들이 오름차순으로 정렬되어 있어야 한다. 하지만 주어진 costs의 값은 그렇지 않다. 그렇기 때문에 미리 정렬을 해주어야 한다.

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

using namespace std;

#define MAX 101

int parentNode[MAX];

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

int ParentNode(int node)
{
    if (parentNode[node] == node)
        return parentNode[node];
    
    return parentNode[node] = ParentNode(parentNode[node]);
}

void MakeSame(int a, int b)
{
    a = ParentNode(a);
    b = ParentNode(b);
    
    if (a < b)
        parentNode[b] = a;
    else
        parentNode[a] = b;
}

bool IsSame(int a, int b)
{
    a = ParentNode(a);
    b = ParentNode(b);
    
    return a == b;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for (int node = 0; node < n; ++node)
        parentNode[node] = node;
    
    sort(costs.begin(), costs.end(), Compare);
    
    for (int i = 0; i < costs.size(); ++i)
    {
        int nodeA = costs[i][0];
        int nodeB = costs[i][1];
        int cost = costs[i][2];
        
        if (IsSame(nodeA, nodeB) == false)
        {
            MakeSame(nodeA, nodeB);
            answer += cost;
        }
    }
    
    return answer;
}

 

---

참고

- 크루스칼 알고리즘 

https://blog.naver.com/ndb796/221230994142