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

문제  : Level3 섬 연결하기

[ 문제출처 ]  https://programmers.co.kr/learn/courses/30/lessons/42861

 

[ 문제풀이 ]

 

이 문제는 n개의 섬에 다리를 건설해야 하는데 

최소의 비용으로 모든 섬을 연결하여야 한다. 

 

다음의 예시를 살펴보면

 

A ----- B ----- C 

 

A----B 와 B----C 를 연결하였으므로 간접적으로 A와 C 는 연결되었다 

즉 A ----- C  A와 C를 연결하는 다리는 건설할 필요 가 없다. 

 

이 문제를 풀기 위해서는 유니온 파인드 알고리즘이 필요하다 

 

유니온 파인드를 적용하면 이 문제는 매우 쉽게 해결 할 수 있다

유니온 파인드에 대해서 잘 모른다면 이에 대해 학습하고 문제 풀기를 추천한다!!

 

모든 노드들을 연결하면서 노드들을 연결하기 위한 모든 비용이

최소가 되어야 한다 

 

[ 소스 코드 ]

#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int parent[100 + 1];
int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}
void Union(int a, int b) {
    a = find(a), b = find(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
bool isSame(int a, int b) {
    return find(a) == find(b);
}
struct Edge {
    int from, to;
    int cost;
    Edge(int u, int v, int w) :from(u), to(v), cost(w) {}
    bool operator < (const Edge& v) {
        return this->cost < v.cost;
    }
};
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<Edge> e;
    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int i = 0; i < costs.size(); i++) {
        e.push_back(Edge(costs[i][0] + 1, costs[i][1] + 1, costs[i][2]));
    }
    sort(e.begin(), e.end());
    for (int i = 0; i < costs.size(); i++) {
        if (!isSame(e[i].from, e[i].to)) Union(e[i].from, e[i].to), answer += e[i].cost;
    }
    return answer;
}