[Lv.3] 섬 연결하기

문제 설명

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

구현해야할 조건

최소 간선을 이어주는 것을 우선으로 풀면 되지만, 나는 MST를 생각해서 문제를 풀었다. 최소 간선트리로 트리를 만들때 제일 값이 적게 들어가는 간선먼저 추가해주는 방식이므로 탐욕법과 유사하다고 생각하는데 이게 맞는지는 체크안해봤다. 이것도 탐욕법이라면 탐욕법일것 같다!

code

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

#define MAX 101
using namespace std;

int parent[MAX];

struct Edge{
    int u,v,weight;
    
    bool operator<(Edge const& e) // compare로 정의해줘도 되는데 이게 더 이쁘다.
    {
        return weight < e.weight; // 무게순으로 정렬해주기
    }
};

int findParent(int node)
{
    if(parent[node] == node)
        return node;
    return parent[node] = findParent(parent[node]); // disjoint set 방식
}

void merge(int node1, int node2)
{
    node1 = findParent(node1);
    node2 = findParent(node2); // 간선으로 이어주기
    
    if(node1 != node2)
    {
        parent[node2] = node1;
    }
}


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    vector<Edge> graph;
    
    for(int i = 0; i < n; i++)
        parent[i] = i;
    
    for(auto& cost : costs)
    {
        graph.push_back({cost[0],cost[1],cost[2]});
    }
    
    sort(graph.begin(),graph.end());
    
    for(int i = 0; i < graph.size(); i++)
    {
        Edge e = graph[i];
                
        if(findParent(e.u) != findParent(e.v))
        {
            merge(e.u,e.v);
            answer += e.weight;
        }
    }
    
//     for(int i = 0; i < n; i++)
//         cout << parent[i] << " ";
    
    
    return answer;
}