[프로그래머스, C++] 섬 연결하기(탐욕 파트)

문제 링크

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

 

 

 

풀이

전형적인 크루스칼 + 유니온파인드 문제다.

최소신장트리(MST)를 만들고 간선에 대해서 모든 비용을 합한다.

 

// cmp 함수

크루스칼 알고리즘을 이용하기 위해 간선(비용)에 대해서 오름차순 정렬한다.

 

// find_root 함수

root 찾는 함수다.

1) root가 지금 나라면 바로 리턴

2) 아니면 나의 부모로 재귀로 호출

 

// solution 함수

map을 이용해 연결됨을 이용했다(어차피 정점에 대해서 중복하지 않으므로)

1) init - 각 정점은 자신을 루트로 지정

2) MST가 만들어질 때까지 반복문을 돌린다(MST는 간선의 수와 (정점의 수-1)이 같을 경우가 최종적으로 만들어진다)

3) 반복문 안에서 root를 찾고 다르면 연결하고 cost 값을 answer에 더해준다 /// root가 같으면 다음 원소로 진행

 

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

using namespace std;

bool cmp(vector<int> v1, vector<int> v2){
    return v1[2] < v2[2];
}

int find_root(map<int, int>& root, int v){
    if(v == root.find(v)->second)
        return v;
    return find_root(root, root.find(v)->second);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // init
    map<int, int> root;
    for(int i=0; i<n; i++){
        root[i] = i;        // 자신을 root로 init
    }
    
    // 비용을 기준으로 오름차순
    sort(costs.begin(), costs.end(), cmp);
    
    // 작은 정점을 기준으로 root 지정
    for(int i=0, count=0; i<costs.size(); i++){
        int root1 = find_root(root, costs[i][0]);
        int root2 = find_root(root, costs[i][1]);
        if(root1 != root2){
            // v2를 v1에 연결
            root.find(root2)->second = root1;
            answer += costs[i][2];      // 비용 추가
            count++;
            if(count == n) break;
        }
    }
    
    return answer;          // 만들 때 필요한 최소 비용
}