프로그래머스: 섬 연결하기

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

 

---

풀이 : 다익스트라알고리즘

 

1. 간선들의 집합을 오름차순을 해준다.

2. 비용이 낮은 간선 부터 선택 ! -> 이때 사이클이 생기는지 검사한다.

 

---

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

using namespace std;

/*class Edge{
    public:
    int node[2];
    int cost ;
    Edge(int x, int y,int cost){
        this->node[0] =x;
        this ->node[1] = y;
        this->cost = cost;
    }
    bool operator < (Edge &edge){
        return this -> cost < edge.cost;
    }
}*/

int getParent(int parent[],int node){
    if(parent[node]==node){
        return node;
    }
    return getParent(parent,parent[node]);
}

int unionParent(int parent[], int x, int y){
    x= getParent(parent,x);
    y= getParent(parent,y);
    if(x<y){
        parent[y] = x;
        return x;
    }else{
        parent[x] = y;
        return y;
    }
}

int findParent(int parent[],int x, int y){
    x = getParent(parent,x);
    y= getParent(parent,y);
    if(x==y){
        return 1; // 같은 부모
    }else{
        return 0; //다른부모
    }
}

bool s_sort(vector<int> temp1, vector<int> temp2){
    int a= temp1[2];
    int b = temp2[2];
    if(a<=b) {
        return true;
    }else{
        return false;
    }
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(), costs.end(),s_sort); // 비용를 오름차순으로 정렬
    // 초기화
    int parents[n];
    for(int i=0; i<n; i++){
        parents[i] = i;
    }
    int sum =0;
    for(int i=0; i<costs.size();i++){
        //다른 부모를 갖게 되는 경우
        if(!findParent(parents,costs[i][0],costs[i][1])){
            sum+=costs[i][2];
            // 연결을 하고 나면, 같은 부모를 갖게 되므로...
            unionParent(parents,costs[i][0],costs[i][1]);
        } // end if
    }// end for

    //결과확인

    return sum;
}

---

Prim 알고리즘의 시간 복잡도
주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복
Prim의 알고리즘의 시간 복잡도는 O(n^2) 이 된다. --> 정점을 기준
Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 이므로 --> 간선을 기준
그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합하고
그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합하다.
https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

[알고리즘] Prim 알고리즘 이란 - Heee's Development Blog

 

따라서 이문제는 간선이 많이 있을수도 있으므로 prim 알고리즘으로도 풀어보자...

---

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

using namespace std;

bool visited[101];
vector<vector<pair<int,int>> > edge;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq; 
int result =0;

void prim(int v){
    visited[v] = true;
    for(int i =0 ; i<edge[v].size(); i++){
        pair<int,int> a = edge[v][i];
        if(!visited[a.second]){
            pq.push(make_pair(a.first, a.second));
        }
    }
    
    while(!pq.empty()){
        pair<int,int> a = pq.top();
        pq.pop();
        if(!visited[a.second]){
            result += a.first;
            prim(a.second);
            return;
        }// 정점이 트리와 연결되지 않았으면 연결한다.
    }//가중치가 낮은 간선을 차례대로 탐색하면서,
}

int solution(int n, vector<vector<int>> costs) {
    edge.resize(n);
    for(int i=0; i<costs.size(); i++){
        int x = costs[i][0];
        int y = costs[i][1];
        int cost = costs[i][2];
        edge[x].push_back(make_pair(cost,y));
        edge[y].push_back(make_pair(cost,x));
    }
    prim(0);
    return result;
}