섬 연결하기

• 섬 연결하기

문제 설명

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

입출력 예

ncostsreturn

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

입출력 예 설명

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

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
int arr[101];
using namespace std;
int f_parent(int x){
    if(arr[x]==x)return x;
    else
        return f_parent(arr[x]);
}
void u_parent(int x, int y){
    x=f_parent(x);
    y=f_parent(y);
    if(x < y)
        arr[y]=x;
    else
        arr[x]=y;
}
bool cmp(vector<int> x, vector<int> y){
    return x[2] <y[2];
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for(int i=0; i<101;i++)
        arr[i]=i;
    
    sort(costs.begin(),costs.end(), cmp);
    
    for(int i =0; i<costs.size();i++){
        int from =costs[i][0];
        int to = costs[i][1];
        int weight =costs[i][2];
        
        if(f_parent(from)!=f_parent(to)){
            u_parent(from,to);
            answer+=weight;
        }
    }
    return answer;
}

 

크루스칼 문제이다. 

크루스칼은 최소한의 비용으로 모든 노드를 연결시키는 방법을 찾는 알고리즘으로 가중치를 기준으로 정렬하고 짧은 것부터 집합에 포함시키면서 사이클을 검사해주면 된다.

순서를 나타내자면

one. 간선의 가중치가 작은 것부터 오름차순으로 정렬한다.

two. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.

     만약 사이클이 발생한다면 신장트리에 포함하지 않는다.

     발생안한다면 최소 신장 트리에 포함시킨다.

three. two의 과정을 간선의 갯수 만큼 반복한다.

 

각 부분을 코드로 나타내면 

one

sort(costs.begin(),costs.end(), cmp);

two

  int from =costs[i][0];
        int to = costs[i][1];
        int weight =costs[i][2];
        
        if(f_parent(from)!=f_parent(to)){
            u_parent(from,to);
            answer+=weight;
        }

three

  for(int i =0; i
        int from =costs[i][0];
        int to = costs[i][1];
        int weight =costs[i][2];
        
        if(f_parent(from)!=f_parent(to)){
            u_parent(from,to);
            answer+=weight;
        }
    }

 

union과 find함수 그리고 arr배열은  사이클의 발생여부를 판단하고 발생하지않는다면 서로의 간선을 이어주는 역활을 하는 건데 나중에 기회가 된다면 저것만 따로 설명하겠따!