프로그래머스 - 섬 연결하기 - Level 3

문제

풀이전략

1. 모든 섬이 연결되도록 하는 최소비용을 구하는 문제이다.
2. 예전에 공부했던 크루스칼 알고리즘을 대입하면 된다. 크루스칼 알고리즘... 잊지말고 기억해야한다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 각 섬을 저장하는 구조체이다. 
struct Edge{
    int v1, v2, val;
    Edge(int a, int b, int c){
        v1 = a;
        v2 = b;
        val = c;
    }
    // 서로 연결하는 비용이 작은순으로 정렬한다. 
    bool operator< (const Edge& v) const{
        return val < v.val;
    }
};
// Union & Find 부분! 핵심파트임
int unf[101];
int Find(int a){
    if(unf[a] == a) return a;
    else return unf[a] = Find(unf[a]);
}
void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    // 서로 연결되지 않을 경우 unf[a] = b 로 해주어 서로 연결시킨다.
    if(a != b){
        unf[a] = b;
    }
}
int solution(int n, vector<vector<int> > costs) {
    int answer = 0;
    int ta, tb, tc;
    vector<Edge> island;
    for(int i=0; i<costs.size(); i++){
        ta = costs[i][0];
        tb = costs[i][1];
        tc = costs[i][2];
        island.push_back(Edge(ta, tb, tc));
        
    }
    for(int i=0; i<n; i++){
        unf[i] = i;
    }
    sort(island.begin(), island.end());
    for(int i=0; i<island.size(); i++){
        if(Find(island[i].v1) != Find(island[i].v2)){
        	// Union을 할때마다 그 이동 비용을 더해준다. 
            answer += island[i].val;
            Union(island[i].v1, island[i].v2);
        }
    }
    return answer;
}

소감

크루스칼 알고리즘..... ㅋㅋㅋ 사실 어려운 알고리즘은 아닌데 항상 기억이 잘 나진 않는다... 잘 기억해야지!