[Programmers] 섬 연결하기

문제 출처 :

 

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

 

 

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 스패닝 트리

 

최소 스패닝 트리의 가장 기본적인 문제가 된다.

 

모든 섬을 연결하기 위해(모든 노드를 연결하기 위해) 최소 가중치 합의 에지를 이용하기 위해서는 최소 스패닝 트리 알고리즘을 이용한다.

 

이때 프림, 크루스칼 중 원하는 알고리즘을 선택하여 문제를 해결한다.

 

 

 

 

 

소스 코드 : 

 

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

using namespace std;
struct KRUSCAL {
    int from, to, val;
};
 
KRUSCAL ks[102];
int ksIdx;
 
int parent[102];
 
bool comp(const KRUSCAL &a, const KRUSCAL &b) {
    return a.val < b.val;
}

int find(int u) {
    if (u == parent[u])
        return u;
 
    return parent[u] = find(parent[u]);
}
 
bool merge(int u, int v) {
    u = find(u);
    v = find(v);
 
    if (u == v)
        return false;
 
    parent[u] = v;
    return true;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for (int i = 0; i < 102; i++)
            parent[i] = i;

    for(int i = 0 ; i < costs.size(); i++){
        ks[i] = { costs[i][0], costs[i][1], costs[i][2] };
    }
    sort(ks, ks + costs.size(), comp);

    for (int i = 0; i < costs.size(); i++)
        if (merge(ks[i].from, ks[i].to)) 
            answer += ks[i].val;
 
    return answer;
}