[C++] 프로그래머스 섬 연결하기

그리디를 사용한다는걸 몰랐다면 알고리즘을 떠올리는데 꽤나 오래 걸렸을 문제.

 

union find 를 이용해야 하는건 알았는데 알고리즘 기억이 안나서 구글링 해서 사용했다. 

요즘엔 구글링 못하게 하는곳도 있다하니 외워두자

 

** 알고리즘

1. costs 의 세번째 인자 (다리 건설 비용) 를 기준으로 오름차순으로 정렬한다.

2. 정렬된 costs 벡터를 인덱스 0부터 탐색하며 만약 두 다리가 연결되지 않았다면 merge 메소드를 통해 연결해준다. 

3. 연결된 다리의 다리 건설 비용을 결과값에 더해준다.

4. 전체 다리가 연결되었으면 반복문을 나간다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int arr[101];
 
void init() {
    for(int i=0; i<101; i++) {
        arr[i] = i;
    }
}
 
int find(int x) {
    if(arr[x] == x) return x;
    return arr[x] = find(arr[x]);
}
 
void merge(int x,int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    arr[y] = x;
}
 
bool isUnion(int x,int y) {
    x = find(x);
    y = find(y);
    
    if(x == y) return true;
    return false;
}
 
bool cmp(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}
 
bool unionCheck(int n) {
    for(int i=0; i<n-1; i++) {
        if(!isUnion(i,i+1)) {return false;}
    }
    return true;
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    init();
    sort(costs.begin(),costs.end(),cmp);
    
    for(int i=0; i<costs.size(); i++) {
        if(isUnion(costs[i][0],costs[i][1])) {continue;}
        merge(costs[i][0],costs[i][1]);
        answer += costs[i][2];
        if(unionCheck(n)) {break;}
    }
    
    
    return answer;
}

 

알고리즘 떠올리는 것 자체만으로는 lv1~2 수준이지만 unionFind가 사용돼 lv3 이 된 문제