[Programmers]탐욕법 > 섬연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861#

코딩테스트 연습 - 섬 연결하기

MST(최소비용신장트리)를 구하는 문제라서 prim, kruskal알고리즘으로 해결 할 수 있다.

 

prim알고리즘으로 구현했다.

1. 모든 노드와 가중치는 prim 2차원 벡터에 저장

2. order는 0부터 시작해서 노드 순서 저장

3. start를 갱신하며 노드 0번부터 pq에 삽입하고 , pq에는 가중치가 제일 작은 원소가 제일 앞에 저장된다.

4. top의 pq.top()[0]번째가 start, [1]번째가 end이고 다음 반복시에는 [1]번째가 start가 되어서 pq에 넣고, 그중 가장 가중치가 작은 맨앞 원소로 다시 start를 [1]번째로 지정하여 반복한다.

5. V에는 가중치가 제일 작은 원소만 저장되어 있다. 마지막에는 항상 노드 한개만 0이어야 한다. V[i]를 모두 더하면  제일 작은 가중치 합을 구할 수 있다.

 

+1.26(수) Kruskal 알고리즘으로도 구현했다.

 

 

Prim 알고리즘으로 구현(c++)

#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <set>
using namespace std;

struct cmp {
    bool operator()(vector<int> a, vector<int> b){
        return a[2] > b[2];
    }
};
int answer = 0;
void Prim(int start, int n , vector<vector<int>> &prim) {
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq; //[2]번째 가중치 기준 오름차순 정렬
    vector<int> order(1,0);
    int V[n]; //각 노드의 가중치 최솟값 저장
    for(int j=0;j<n;j++)V[j] = 0;
    
    while (1) {
        for(int i=0;i<n;i++){ //한번 push한 원소는 가중치 0으로 업데이트해서 재사용되지 않게 하기
            if(prim[start][i] != 0) { pq.push({start, i, prim[start][i]}); prim[start][i] = 0; prim[i][start] = 0; }
        }
        if(V[start] != 0 || pq.top()[2] == 0 ) {pq.pop(); continue;}
        for(int j=0;j<order.size();j++)if(order[j] == pq.top()[1]) {pq.pop();j=-1;}
        
        V[start] = pq.top()[2];
        start = pq.top()[1]; //start를 이전의 도착지점으로 설정
        
        order.push_back(start);
        pq.pop();
        
        if(count(V, V+n, 0) == 1) break;
    }
   
    answer = accumulate(V, V+n, 0);
}
 
int solution(int n, vector<vector<int>> costs) {
    vector<vector<int>> prim(n, vector<int>(n, 0));
    for(int i = 0; i < costs.size(); i++) {
        prim[costs[i][0]][costs[i][1]] = costs[i][2];
        prim[costs[i][1]][costs[i][0]] = costs[i][2];
    }
    
    Prim(0, n, prim);
    return answer;
    
}

 

 

---

Kruskal알고리즘은 https://blog.naver.com/ndb796/221230994142 동빈나님 블로그를 참고했다.

 

1. 가중치가 낮은 순서대로 간선을 오름차순으로 정렬
2. 오름차순으로 정렬 된 간선 중 사이클이 형성되는지 check함수로 확인
   • 노드들의 루트(부모)를 확인해서, 부모가 같지 않을때만 간선을 선택함
3. 선택한 간선을 union시킴. 두 부모중 더 작은 값을 루트로 삼아서 연결.

 

Kruskal 알고리즘으로 구현(c++)

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

using namespace std;

bool comp(vector<int> a, vector<int> b){
    return a[2] < b[2];
}
int rootNode(int parent[], int x){
    if(parent[x] == x ) return x;
    return parent[x] = rootNode(parent, parent[x]);
}

bool check(int parent[], int a, int b){
    int a_parent = rootNode(parent, a);
    int b_parent = rootNode(parent, b);
    if(a_parent == b_parent) return true;
    else return false;
}
void unionNode(int parent[], int a, int b){
    int a_parent = rootNode(parent, a);
    int b_parent = rootNode(parent, b);
    if(a_parent < b_parent) parent[b_parent] = a_parent;
    else parent[a_parent] = b_parent;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int edge = 0;
    //1. 가중치 순서대로 간선 오름차순 정렬
    sort(costs.begin(), costs.end(), comp);
   
    int parent[n];
    for(int i=0;i<n;i++)parent[i] = i;
    
    for(int i=0;i<costs.size();i++){
        if(edge == n-1) break;
        //2. 오름차순 정렬된 간선 중 사이클 형성하지 않는 간선 선택
        if(!check(parent, costs[i][0], costs[i][1])){
            //3. 선택한 간선을 MST 집합에 union
            unionNode(parent, costs[i][0], costs[i][1]);
            answer += costs[i][2];
            edge++;
        }
    }
    return answer;
}

---

시도한 테스트케이스

[[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]] 4 => 4

[[0, 1, 5], [1, 2, 3], [2, 3, 3], [3, 1, 2], [3, 0, 4]] 4 => 9

[[0, 1, 5], [1, 2, 3], [2, 3, 3], [3, 1, 2], [3, 0, 4], [2, 4, 6], [4, 0, 7]] 5 => 15