[Programmres/C++] 섬 연결하기

시간 복잡도

• Kruskal의 최소 신장 트리를 이용하여 구현하면 $O(ElogE)$의 시간 복잡도가 발생합니다.

문제 접근법

• 최소 신장 트리(MST)를 이용하여 문제를 해결할 수 있습니다.

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct Edge
{
    int start, end, weight;
    
    bool operator> (const Edge& edge) const
    {
        return weight > edge.weight;
    }
};

static int parent[101]={};
static priority_queue<Edge, vector<Edge>, greater<>> pq;

int Find(int node);
void Union(int a, int b);
int MST(int N);


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for(int i=0; i<n; i++)
        parent[i]=i;
    
    for(vector<int> v : costs)
    {
        int start = v[0];
        int end = v[1];
        int weight = v[2];
        
        pq.push({start, end, weight});
    }
    
    answer = MST(n);
    
    return answer;
}

int Find(int a)
{
    if(parent[a]==a)
        return a;
    
    return parent[a] = Find(parent[a]);
}

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

int MST(int N)
{
    int result=0;
    int usedEdge=0;
    
    while(usedEdge < N-1)
    {
        const auto [start, end, weight] = pq.top();
        pq.pop();
                
        if(Find(start) != Find(end))
        {
            Union(start, end);
            result+=weight;
            usedEdge++;
        }
    }
    
    return result;
}