[Programmers] 섬 연결하기

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

프로그래머스

 

---

 

문제 해결 과정

착안

문제에서 요구하는 결과값이 최소 신장 트리(minimum spanning tree)의 간선의 가중치의 총합이므로, 최소 신장 트리 알고리즘을 활용하여 문제를 해결하고자 하였다.

 

구현

간선 데이터가 주어지므로, 유니온-파인드(union-find) 연산을 구현한 다음 크루스칼 알고리즘(Kruskal's algorithm)을 통해 최소 신장 트리를 만들어 가중치의 총합을 구하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>
#include <algorithm>

using namespace std;

int Parent[100];

int Find(int a)
{
    int temp = a;
    while (a != Parent[a])
        a = Parent[a];
    return Parent[temp] = a;
}

void Union(int a, int b)
{
    if (Find(a) != Find(b))
        Parent[Parent[b]] = a;
}

int solution(int n, vector<vector<int>> costs)
{
    for (int i = 0; i < n; i++)
        Parent[i] = i;
    
    sort(costs.begin(),
         costs.end(),
         [](const vector<int>& a, const vector<int>& b)
         {
             return a[2] < b[2];
         });
    
    int answer = 0;
    for (vector<int> cost : costs)
    {
        if (Find(cost[0]) != Find(cost[1]))
        {
            Union(cost[0], cost[1]);
            answer += cost[2];
        }
    }
    
    return answer;
}

 

실행 결과