[프로그래머스] - 섬 연결하기(C/C++)

프로그래머스

[문제 설명]

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

---

[문제 풀이]

[Algorithm] - Union-Find(Disjoint-set)

 

[Algorithm] - Kruskal's Algorithm(최소 스패닝 트리)

섬 연결하기 문제를 풀기 위해 공부해야했던 알고리즘이다.

Union-Find->Kruskal's Algorithm 순서로 해야 이해될 수 있다.

섬 연결하기 문제가 크러스컬 알고리즘 자체라고 생각한다. 그렇기에 Kruskal's Algorithm 포스트에도 동일한 코드가 들어가있다.

 

이 문제를 풀때 조심해야 할 것은,

입력으로 들어오는 간선의 수(costs.size)의 최대값은 ((n-1) * n) / 2 이면서, n보다 작을수 있다는 것이다.

Union-Find를 하기위해 배열을 초기화해주어야 하는데, 이때 costs 크기만큼 초기화해주면서 뒷부분이 제대로 계산되지 않는 문제가 있었다.

 

다들 나처럼 바보같은 실수를 하지 않기를....

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> unf(4951);

struct Edge{
    int v1_;
    int v2_;
    int cost_;
    
    Edge(int v1, int v2, int cost) : v1_(v1), v2_(v2), cost_(cost) {} 
    
    bool operator<(Edge& b)
    {
        return cost_ < b.cost_;
    }
};

int parentFind(int a)
{
    if(a == unf[a]) return a;
    else return unf[a] = parentFind(unf[a]);
}

void parentUnion(int a, int b)
{
    a = parentFind(a);
    b = parentFind(b);
    if(a != b) unf[a] = b;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<Edge> v;
    int costSize = costs.size();
    for(int i =0; i < costSize; i++)
    {
        v.push_back(Edge(costs[i][0],costs[i][1],costs[i][2]));
    }
    
    for(int i =0; i <= n; i++)
    {
        unf[i] = i;
    }
    
    sort(v.begin(), v.end());

    for(int i =0; i < costSize; i++)
    {
        int parentV1 = parentFind(v[i].v1_);
        int parentV2 = parentFind(v[i].v2_);
        if(parentV1 != parentV2)
        {
            parentUnion(v[i].v1_, v[i].v2_); 
            answer += v[i].cost_;
        }
    }
    return answer;
}